test/aoj/dijkstra.test.cpp

• View this file on GitHub
• Last update: 2023-04-08 02:15:04+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/GRL_1_A

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/GRL_1_A"
#include <queue>
#include <bits/stdc++.h>
using namespace std;

constexpr int INF = 11e8;

int main() {
  int v,e,r; cin>>v>>e>>r;
  vector<pair<int,int>> G[v];
  for (int i = 0; i < e; i++) {
    int s,t,d; cin>>s>>t>>d;
    G[s].emplace_back(t, d);
  }

  vector<int> dist(v, INF);
  priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> qs;
  dist[r] = 0;
  qs.emplace(0, r);
  while (!qs.empty()) {
    auto [c, s] = qs.top(); qs.pop();
    if (dist[s] < c) continue;
    for (auto [t, d] : G[s]) {
      if (dist[t] <= c + d) continue;
      dist[t] = c + d;
      qs.emplace(c + d, t);
    }
  }
  for (int i = 0; i < v; i++) {
    if (dist[i] != INF) {
      cout << dist[i] << endl;
    } else {
      cout << "INF" << endl;
    }
  }

}

#line 1 "test/aoj/dijkstra.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/GRL_1_A"
#include <queue>
#include <bits/stdc++.h>
using namespace std;

constexpr int INF = 11e8;

int main() {
  int v,e,r; cin>>v>>e>>r;
  vector<pair<int,int>> G[v];
  for (int i = 0; i < e; i++) {
    int s,t,d; cin>>s>>t>>d;
    G[s].emplace_back(t, d);
  }

  vector<int> dist(v, INF);
  priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> qs;
  dist[r] = 0;
  qs.emplace(0, r);
  while (!qs.empty()) {
    auto [c, s] = qs.top(); qs.pop();
    if (dist[s] < c) continue;
    for (auto [t, d] : G[s]) {
      if (dist[t] <= c + d) continue;
      dist[t] = c + d;
      qs.emplace(c + d, t);
    }
  }
  for (int i = 0; i < v; i++) {
    if (dist[i] != INF) {
      cout << dist[i] << endl;
    } else {
      cout << "INF" << endl;
    }
  }

}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	6 ms	3 MB
g++	00_sample_01.in	AC	5 ms	3 MB
g++	01_small_00.in	AC	5 ms	3 MB
g++	01_small_01.in	AC	5 ms	3 MB
g++	02_medium_00.in	AC	5 ms	3 MB
g++	02_medium_01.in	AC	5 ms	3 MB
g++	03_corner_00.in	AC	5 ms	3 MB
g++	03_corner_01.in	AC	5 ms	3 MB
g++	03_corner_02.in	AC	5 ms	3 MB
g++	03_corner_03.in	AC	5 ms	3 MB
g++	04_rand_00.in	AC	5 ms	3 MB
g++	04_rand_01.in	AC	5 ms	3 MB
g++	04_rand_02.in	AC	5 ms	3 MB
g++	04_rand_03.in	AC	6 ms	3 MB
g++	05_linear_00.in	AC	5 ms	3 MB
g++	05_linear_01.in	AC	5 ms	3 MB
g++	05_linear_02.in	AC	5 ms	3 MB
g++	05_linear_03.in	AC	5 ms	3 MB
g++	06_ring_00.in	AC	5 ms	3 MB
g++	06_ring_01.in	AC	5 ms	3 MB
g++	06_ring_02.in	AC	5 ms	3 MB
g++	06_ring_03.in	AC	5 ms	3 MB
g++	07_large_00.in	AC	6 ms	3 MB
g++	07_large_01.in	AC	7 ms	4 MB
g++	07_large_02.in	AC	8 ms	4 MB
g++	07_large_03.in	AC	10 ms	4 MB
g++	08_large_00.in	AC	18 ms	4 MB
g++	08_large_01.in	AC	21 ms	4 MB
g++	08_large_02.in	AC	25 ms	4 MB
g++	08_large_03.in	AC	35 ms	5 MB
g++	09_maximum_00.in	AC	168 ms	8 MB
g++	09_maximum_01.in	AC	380 ms	13 MB
g++	09_maximum_02.in	AC	141 ms	9 MB
g++	09_maximum_03.in	AC	216 ms	10 MB
clang++	00_sample_00.in	AC	6 ms	3 MB
clang++	00_sample_01.in	AC	5 ms	3 MB
clang++	01_small_00.in	AC	5 ms	3 MB
clang++	01_small_01.in	AC	5 ms	3 MB
clang++	02_medium_00.in	AC	5 ms	3 MB
clang++	02_medium_01.in	AC	5 ms	3 MB
clang++	03_corner_00.in	AC	5 ms	3 MB
clang++	03_corner_01.in	AC	5 ms	3 MB
clang++	03_corner_02.in	AC	5 ms	3 MB
clang++	03_corner_03.in	AC	5 ms	3 MB
clang++	04_rand_00.in	AC	5 ms	3 MB
clang++	04_rand_01.in	AC	5 ms	3 MB
clang++	04_rand_02.in	AC	5 ms	3 MB
clang++	04_rand_03.in	AC	5 ms	3 MB
clang++	05_linear_00.in	AC	5 ms	3 MB
clang++	05_linear_01.in	AC	5 ms	3 MB
clang++	05_linear_02.in	AC	5 ms	3 MB
clang++	05_linear_03.in	AC	5 ms	3 MB
clang++	06_ring_00.in	AC	5 ms	3 MB
clang++	06_ring_01.in	AC	5 ms	3 MB
clang++	06_ring_02.in	AC	5 ms	3 MB
clang++	06_ring_03.in	AC	5 ms	3 MB
clang++	07_large_00.in	AC	6 ms	3 MB
clang++	07_large_01.in	AC	7 ms	3 MB
clang++	07_large_02.in	AC	9 ms	4 MB
clang++	07_large_03.in	AC	10 ms	4 MB
clang++	08_large_00.in	AC	20 ms	4 MB
clang++	08_large_01.in	AC	24 ms	4 MB
clang++	08_large_02.in	AC	29 ms	4 MB
clang++	08_large_03.in	AC	38 ms	5 MB
clang++	09_maximum_00.in	AC	158 ms	8 MB
clang++	09_maximum_01.in	AC	384 ms	14 MB
clang++	09_maximum_02.in	AC	142 ms	9 MB
clang++	09_maximum_03.in	AC	211 ms	10 MB

Back to top page