test/aoj-grl-1-a.test.cpp

• View this file on GitHub
• Last update: 2021-05-27 02:04:57+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A

Depends on

• graph/dijkstra.hpp

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A"
#include <iostream>
#include <vector>
#include "../graph/dijkstra.hpp"

int main(){
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  int V, E, r; 
  std::cin >> V >> E >> r;
  std::vector<std::vector<std::pair<int, long long>>> g(V);
  for(int i=0; i<E; i++) {
    int s, t, d; std::cin >> s >> t >> d;
    g[s].push_back({t, d});
  }
  
  auto d = dijkstra<long long>(g, r, 0);
  for(int i=0; i<V; i++) {
    if(d[i] == (1LL<<60)) std::cout << "INF" << '\n';
    else std::cout << d[i] << '\n';
  }
  
  return 0;
}

#line 1 "test/aoj-grl-1-a.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A"
#include <iostream>
#include <vector>
#line 1 "graph/dijkstra.hpp"
#include<queue>
#line 3 "graph/dijkstra.hpp"
template<typename T>
std::vector<T> dijkstra(std::vector<std::vector<std::pair<int, T>>> &g, int s, int t) {
  std::vector<T> dist(g.size(), (1LL<<60));
  dist[s] = 0;
  std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int>>, std::greater<std::pair<T, int>>> pq;
  pq.push({0, s});
  while(pq.size()) {
    auto[prec, v] = pq.top(); pq.pop();
    if(dist[v] < prec) continue;
    for(auto[u, cost]: g[v]) {
      if(dist[u] > dist[v] + cost) {
        dist[u] = dist[v] + cost;
        pq.push({dist[u], u});
      }
    }
  }
  return dist;
}
#line 5 "test/aoj-grl-1-a.test.cpp"

int main(){
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  int V, E, r; 
  std::cin >> V >> E >> r;
  std::vector<std::vector<std::pair<int, long long>>> g(V);
  for(int i=0; i<E; i++) {
    int s, t, d; std::cin >> s >> t >> d;
    g[s].push_back({t, d});
  }
  
  auto d = dijkstra<long long>(g, r, 0);
  for(int i=0; i<V; i++) {
    if(d[i] == (1LL<<60)) std::cout << "INF" << '\n';
    else std::cout << d[i] << '\n';
  }
  
  return 0;
}

Back to top page