#2108213

Solution for GRL_1_A: Single Source Shortest Path by tuc_lt

Source Code Status Test Cases
    Policy: public     Reviewed: 7    
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 #  ( | )


Comments
 
 Under Construction.
 
Categories
 
 
Free Tags