Test/AOJ/Dijkstra.test.cpp

• View this file on GitHub
• Last update: 2022-03-14 20:21:31+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_A

Depends on

• Dijkstra (Graph/Dijkstra.cpp)
• Other/Template.cpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_A"

#include<bits/stdc++.h>
using namespace std;

#include"../../Other/Template.cpp"
#include"../../Graph/Dijkstra.cpp"

int main() {
    int N,M,r;
    cin >> N >> M >> r;
    vector<vector<Edge<int>>> graph(N);
    for(int i = 0;i < M;i++) {
        int s,t,d;
        cin >> s >> t >> d;
        graph[s].push_back({t,d});
    }
    vector<int> dist = dijkstra(N,graph,r);
    for(const auto& x:dist) {
        if(x == numeric_limits<int>::max()) cout << "INF" << endl;
        else cout << x << endl;
    }
}

#line 1 "Test/AOJ/Dijkstra.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_A"

#include<bits/stdc++.h>
using namespace std;

#line 1 "Other/Template.cpp"
constexpr int Inf = 2000000030;
constexpr long long INF= 2000000000000000000;

template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
#line 1 "Graph/Dijkstra.cpp"
template<typename T>
struct Edge {
    int to;
    T cost;
};

std::vector<int> pre;

template<typename T>
std::vector<T> dijkstra(const int& node,const vector<vector<Edge<T>>>& graph,const int& start) {
    std::priority_queue<pair<T,int>,vector<pair<T,int>>,greater<pair<T,int>>> que;
    vector<T> dist(node,numeric_limits<T>::max());
    pre = vector<int>(node,-1);
    dist[start] = 0;
    que.push({0,start});

    while(!que.empty()) {
        auto [cost,v] = que.top();
        que.pop();
        if(dist[v] < cost) continue;
        for(const auto& [to,d]:graph[v]) {
            if(dist[to] > dist[v] + d) {
                dist[to] = dist[v] + d;
                pre[to] = v;
                que.push({dist[to],to});
            }
        }
    }

    return dist;
}

vector<int> GetPath(int t) {
    vector<int> path;

    while(t != -1) {
        path.push_back(t);
        t = pre[t];
    }

    reverse(path.begin(),path.end());
    return path;
}
#line 8 "Test/AOJ/Dijkstra.test.cpp"

int main() {
    int N,M,r;
    cin >> N >> M >> r;
    vector<vector<Edge<int>>> graph(N);
    for(int i = 0;i < M;i++) {
        int s,t,d;
        cin >> s >> t >> d;
        graph[s].push_back({t,d});
    }
    vector<int> dist = dijkstra(N,graph,r);
    for(const auto& x:dist) {
        if(x == numeric_limits<int>::max()) cout << "INF" << endl;
        else cout << x << endl;
    }
}

Back to top page