## #2108213

Solution for GRL_1_A: Single Source Shortest Path by tuc_lt

Source Code Status Test Cases
Policy: public     Reviewed: 29
00.15 sec    17008 KB    97 lines     1823 bytes    2016-12-06 11:34
```#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fst first
#define snd second
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl
#define INF INT_MAX/2

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
template<class T> using vv=vector<vector< T > >;

struct Edge {
int cost;
int to;
};

int n;
vv<Edge> g;
vector<int> d;

void dijkstra(int s) {
d.assign(n, INF);
priority_queue<vi, vector<vi>, greater<vi> > q;
d[s] = 0;
q.push({0, s}); // candidate of min-cost, edge number

while (!q.empty()) {
auto p = q.top(); // delete from queue
q.pop();
int v = p[1];
if (d[v] < p[0]) {
continue;
}
for (auto e : g[v]) {
if (d[e.to] > d[v] + e.cost) {
d[e.to] = d[v] + e.cost;
q.push({d[e.to], e.to});
}
}
}
}

int main() {
int ne, s;
scanf("%d %d %d", &n, &ne, &s);
g.resize(n);
rep (i, ne) {
int a, b, d;
scanf("%d %d %d", &a, &b, &d);
Edge e;
e.cost = d;
e.to = b;
g[a].pb(e);
}
dijkstra(s);
rep (i, n) {
if (d[i] == INF) {
printf("INF\n");
} else {
printf("%d\n", d[i]);
}
}

return 0;
}

```
 Compile Error Logs: You are not authorized to see the message.

Status
 Judge: 34/34 C++14 CPU: 00.15 sec Memory: 17008 KB Length: 1823 B 2016-12-06 11:34 2016-12-06 11:34
Results for testcases
 Case # Verdict CPU Time Memory In Out Case Name Case #1: : Accepted 00.00 sec 3104 KB Case #2: : Accepted 00.00 sec 3212 KB Case #3: : Accepted 00.00 sec 3252 KB Case #4: : Accepted 00.00 sec 3212 KB Case #5: : Accepted 00.00 sec 3056 KB Case #6: : Accepted 00.00 sec 3060 KB Case #7: : Accepted 00.00 sec 3172 KB Case #8: : Accepted 00.00 sec 3252 KB Case #9: : Accepted 00.00 sec 3252 KB Case #10: : Accepted 00.00 sec 3204 KB Case #11: : Accepted 00.00 sec 3104 KB Case #12: : Accepted 00.00 sec 3048 KB Case #13: : Accepted 00.00 sec 3244 KB Case #14: : Accepted 00.00 sec 3212 KB Case #15: : Accepted 00.00 sec 3120 KB Case #16: : Accepted 00.00 sec 3204 KB Case #17: : Accepted 00.00 sec 3144 KB Case #18: : Accepted 00.00 sec 3140 KB Case #19: : Accepted 00.00 sec 3136 KB Case #20: : Accepted 00.00 sec 3140 KB Case #21: : Accepted 00.00 sec 3212 KB Case #22: : Accepted 00.00 sec 3176 KB Case #23: : Accepted 00.00 sec 3160 KB Case #24: : Accepted 00.00 sec 3124 KB Case #25: : Accepted 00.00 sec 3268 KB Case #26: : Accepted 00.00 sec 3252 KB Case #27: : Accepted 00.00 sec 3488 KB Case #28: : Accepted 00.00 sec 3632 KB Case #29: : Accepted 00.00 sec 3828 KB Case #30: : Accepted 00.00 sec 4140 KB Case #31: : Accepted 00.06 sec 8412 KB Case #32: : Accepted 00.15 sec 17008 KB Case #33: : Accepted 00.03 sec 8516 KB Case #34: : Accepted 00.08 sec 10444 KB
 < prev | / | next >

 Judge Input #  ( | ) Judge Output #  ( | )