Submission #00009

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define int long long
main(){
    int n,m;cin>>n>>m;
    vector<int>t(n+1,LONG_LONG_MAX);
    vector<vector<int>>s(n+1,vector<int>(0));
    t[1]=0;
    int a[m],b[m],c[m];
    for(int i=0;i<m;i++){
        cin>>a[i]>>b[i]>>c[i];
        s[a[i]].push_back(b[i]);
    }
    queue<int>q;
    for(int i=0;i<=n+1;i++){
        for(int j=0;j<m;j++){
            if(t[a[j]]!=LONG_LONG_MAX){
                if(t[a[j]]+c[j] < t[b[j]]){
                    t[b[j]] = t[a[j]]+c[j];
                    if(i==n+1){
                        q.push(b[j]);
                    }
                }
            }
        }
    }
    if(t[n]==LONG_LONG_MAX){
        cout<<"-1\n";
        return(0);
    }
    vector<bool>y(n+1,true);
    while(!q.empty()){
        int now=q.front();
        q.pop();
        if(y[now]){
            y[now]=false;
            for(int i=0;i<s[now].size();i++){
                if(y[s[now][i]]){
                    y[s[now][i]]=false;
                    q.push(s[now][i]);
                }
            }
        }
    }
    if(y[n]){
        cout<<t[n]<<"\n";
    }else{
        cout<<"-1\n";
    }
}

ステータス

項目	データ
問題	0004 - Shortest Path2
ユーザー名	ei2326
投稿日時	2024-08-09 10:10:58
言語	C++17
状態	Accepted
得点	10
ソースコード長	1211 Byte
最大実行時間	59 ms
最大メモリ使用量	980 KB

セット

	セット	得点	Cases
1	ALL	10 / 10	*

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
in1.txt	AC	26 ms	600 KB	1
in2.txt	AC	26 ms	444 KB	1
in3.txt	AC	23 ms	544 KB	1
in4.txt	AC	23 ms	512 KB	1
in5.txt	AC	50 ms	864 KB	1
in6.txt	AC	59 ms	980 KB	1
in7.txt	AC	29 ms	804 KB	1
in8.txt	AC	42 ms	736 KB	1
in9.txt	AC	24 ms	552 KB	1