結果

問題 No.1601 With Animals into Institute
ユーザー ytft
提出日時 2021-12-29 21:42:11
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,964 bytes
コンパイル時間 1,828 ms
コンパイル使用メモリ 186,168 KB
実行使用メモリ 114,740 KB
最終ジャッジ日時 2024-10-04 14:02:00
合計ジャッジ時間 8,546 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other WA * 6 TLE * 3 -- * 27
権限があれば一括ダウンロードができます

ソースコード

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