verify/aoj/dijkstra.test.cpp

View this file on GitHub
Last update: 2023-03-24 23:12:28-07:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A"

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

#include "../../graph/dijkstra.hpp"

int main(){
    int V,E,r;
    cin>>V>>E>>r;
    WeightedGraph<int> g=input_wgraph<int>(V,E,true,false);
    vector<int> ans=dijkstra<int>(g,r);

    for(int i=0;i<V;i++){
        if(ans[i]==-1){
            cout<<"INF"<<endl;
        }else{
            cout<<ans[i]<<endl;
        }
    }
}

#line 1 "verify/aoj/dijkstra.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A"

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

#line 3 "graph/graph-template.hpp"
template<class T>
struct edge{
    int from,to;
    T cost;
    
    edge(int to,T cost):from(-1),to(to),cost(cost){}
    edge(int from,int to,T cost):from(from),to(to),cost(cost){}

    edge &operator=(const int &x){
        to=x;
        return *this;
    }
};

template<class T>
using Edges = std::vector<edge<T>>;

template<class T>
using WeightedGraph = std::vector<Edges<T>>;
using UnweightedGraph = std::vector<std::vector<int>>;

UnweightedGraph input_graph(int N,int M,bool directed=false,bool one_origin=true){
    UnweightedGraph ret(N);
    for(int i=0;i<M;i++){
        int from,to;std::cin>>from>>to;
        if(one_origin)from--,to--;
        ret[from].push_back(to);
        if(!directed)ret[to].push_back(from);
    }
    return ret;
};

template<class T>
WeightedGraph<T> input_wgraph(int N,int M,bool directed=false,bool one_origin=true){
    WeightedGraph<T> ret(N);
    for(int i=0;i<M;i++){
        int from,to;T cost;std::cin>>from>>to>>cost;
        if(one_origin)from--,to--;
        ret[from].emplace_back(from,to,cost);
        if(!directed)ret[to].emplace_back(to,from,cost);
    }
    return ret;
};
#line 2 "graph/dijkstra.hpp"

#line 6 "graph/dijkstra.hpp"

template<class T>
std::vector<T> dijkstra(WeightedGraph<T> &graph,int start=0){
    int n=(int)graph.size();
    std::vector<T> dist(n,(T)-1);
    std::vector<bool> ok(n,false);

    std::priority_queue<std::pair<T,int>,std::vector<std::pair<T,int>>,std::greater<std::pair<T,int>>> Q;
    dist[start]=0;
    Q.push({dist[start],start});

    while(!Q.empty()){
        int pos=Q.top().second;Q.pop();
        if(ok[pos])continue;
        ok[pos]=true;
        for(int i=0;i<(int)graph[pos].size();i++){
            if(dist[graph[pos][i].to]==-1 || dist[graph[pos][i].to]>dist[pos]+graph[pos][i].cost){
                dist[graph[pos][i].to]=dist[pos]+graph[pos][i].cost;
                Q.push({dist[graph[pos][i].to],graph[pos][i].to});
            }
        }
    }

    return dist;
}
#line 7 "verify/aoj/dijkstra.test.cpp"

int main(){
    int V,E,r;
    cin>>V>>E>>r;
    WeightedGraph<int> g=input_wgraph<int>(V,E,true,false);
    vector<int> ans=dijkstra<int>(g,r);

    for(int i=0;i<V;i++){
        if(ans[i]==-1){
            cout<<"INF"<<endl;
        }else{
            cout<<ans[i]<<endl;
        }
    }
}