Submission 835 | MatCom Online Grader

Id	Date	User	Problem	Result	Time	Mem	Lang
835	15/05/2013 23:00:32	leandro	C - Pueblos y caminos	Accepted	140	6.6 KiB	GNU G++ 5.1.0

Code

/*
    username: leandro
*/

#include <cstdio>
#include <queue>
#include <iostream>
#define i64 long long

using namespace std;

const int
      MaxV = 5000 + 10,
	  MaxE = 200000 + 10;

const i64
      oo = 1LL << 40LL;

typedef pair<i64, int> pii;

struct edg {
    int dest;
	i64 cost;
	int next;
	edg() { }
	edg(int dest, i64 cost, int next) :
	    dest(dest), cost(cost), next(next) { }
};

int i, j;
int A, B;
int V, E, K;
int node[MaxV];
i64 coin[MaxV];
bool bio[MaxV];
int first[MaxV];
edg edges[MaxE];
i64 distA[MaxV];
i64 distB[MaxV];
priority_queue <pii> Q;

void shortest_path(i64* dist, int source) {
    for (i = 1; i <= V; i++) {
	    bio[i] = false;
		dist[i] = oo;
	}
	dist[source] = 0;
	Q.push(pii(0, source));
	while (!Q.empty()) {
	    i64 c = -Q.top().first;
		int a = Q.top().second;
		Q.pop();
		if (bio[a])
		    continue;
		bio[a] = true;
		for (i = first[a]; i; i = edges[i].next)
		    if (dist[ edges[i].dest ] > c + edges[i].cost) {
			    dist[ edges[i].dest ] = c + edges[i].cost;
				Q.push(pii(-dist[ edges[i].dest ], edges[i].dest));
			}
	}
}

int main()
{
	cin.sync_with_stdio(false);

cin >> V >> E >> K;
	cin >> A >> B;

for (i = 1; i <= K; i++)
	    cin >> node[i] >> coin[i];

for (i = 1; i <= E; i++) {
	    int a, b; i64 c;
		cin >> a >> b >> c;
		edges[i]   = edg(b, c, first[a]);
		edges[i+E] = edg(a, c, first[b]);
		first[a] = i; first[b] = i + E;
	}

shortest_path(distA, A);
	shortest_path(distB, B);

i64 sol = oo;
	for (i = 1; i <= K; i++)
	    sol = min(sol, distA[ node[i] ] + distB[ node[i] ] + coin[i]);

cout << sol << endl;

return 0;
}

Judgement Details

Test 01: 0.018 0.000 1428K ok
Test 02: 0.017 0.000 1720K ok
Test 03: 0.027 0.016 1828K ok
Test 04: 0.028 0.016 1980K ok
Test 05: 0.167 0.109 6480K ok
Test 06: 0.023 0.016 1920K ok
Test 07: 0.177 0.140 6748K ok
Test 08: 0.183 0.109 6784K ok
Test 09: 0.221 0.078 6788K ok
Test 10: 0.181 0.094 6780K ok
Test 11: 0.201 0.062 6792K ok
Test 12: 0.011 0.000 1424K ok
Test 13: 0.159 0.125 6776K ok
Test 14: 0.010 0.000 1428K ok
Test 15: 0.011 0.000 1428K ok
Test 16: 0.012 0.000 1428K ok
Test 17: 0.062 0.000 1436K ok
Test 18: 0.021 0.000 1712K ok
Test 19: 0.035 0.016 2444K ok
Test 20: 0.014 0.000 1568K ok
Accepted

Matcom Online Grader