結果

問題 No.1601 With Animals into Institute
ユーザー ytftytft
提出日時 2021-12-29 21:42:11
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,964 bytes
コンパイル時間 1,848 ms
コンパイル使用メモリ 181,912 KB
実行使用メモリ 112,568 KB
最終ジャッジ日時 2024-04-15 03:42:26
合計ジャッジ時間 8,085 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 TLE -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

struct directedGraph{
    int N;
    vector<int> edgesValue;
    vector<vector<int>> edges;
    directedGraph(int n){
        N=n;
    }
    void addEdge(int a,int b,int value=0){
        edges.emplace_back((vector<int>){a,b});
        edgesValue.emplace_back(value);
    }
    vector<vector<int>> getConnection(){
        vector<vector<int>> ret(N,vector<int>(0));
        for(vector<int> v:edges){
            ret[v[0]].emplace_back(v[1]);
        }
        return ret;
    }
    vector<int> dijkstra(int start){
        vector<vector<int>> connection=getConnection();
        map<int,int> cost;
        for(int i=edges.size()-1;i>=0;--i){
            cost[edges[i][0]*N+edges[i][1]]=edgesValue[i];
        }
        vector<int> ret(N,INT_MAX);
        auto comp=[](vector<int> a,vector<int> b) {
            return a[1]>b[1];
        };
        priority_queue<vector<int>,vector<vector<int>>,decltype(comp)> que{comp};
        que.push((vector<int>){start,0});
        ret[start]=0;
        while(!que.empty()){
            vector<int> temp=que.top();
            que.pop();
            for(int i:connection[temp[0]]){
                if(cost[temp[0]*N+i]+ret[temp[0]]<ret[i]){
                    ret[i]=cost[temp[0]*N+i]+ret[temp[0]];
                    que.push((vector<int>){i,ret[i]});
                }
            }
        }
        return ret;
    }
};


int main(){
    int N,M,A,B,C,T;
    cin>>N>>M;
    directedGraph G(N*2);
    for(int i=0;i<M;++i){
        cin>>A>>B>>C>>T;
        --A;
        --B;
        if(T){
            G.addEdge(A+N,B,C);
            G.addEdge(A,B,C);
            G.addEdge(B+N,A,C);
            G.addEdge(B,A,C);
        }else{
            G.addEdge(A,B,C);
            G.addEdge(A+N,B+N,C);
            G.addEdge(B,A,C);
            G.addEdge(B+N,A+N,C);
        }
    }
    vector<int> ans=G.dijkstra(2*N-1);
    for(int i=0;i<N-1;++i){
    	cout<<ans[i]<<endl;
    }
}
0