Submission #58105

ソースコード

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int,int>P;
const int INF=1<<30;
int main(){
  int n,m;
  int min_cost[100005];
  vector<P>node[100005];
  cin>>n>>m;
  for(int i=0;i<=n;i++){
    min_cost[i]=INF;
  }
  for(int i=0;i<m;i++){
    int a,b,c;
    cin>>a>>b>>c;
    node[a].push_back(P(b,c));
    node[b].push_back(P(a,c));
  }
   
  priority_queue<P,vector<P>,greater<P> >pq;
  pq.push(P(0,1));
  min_cost[1]=0;
  while(!pq.empty()){
    P now=pq.top();pq.pop();
    int cost=now.first;
    int pos=now.second;
    if(min_cost[pos]==cost){/*********重要！！！***********/
      for(int i=0;i<node[pos].size();i++){
        int next=node[pos][i].first;
        int ncost=node[pos][i].second+cost;
        if(ncost<min_cost[next]){//ここも注意
          min_cost[next]=ncost;
          pq.push(P(ncost,next));
        }
      }
    }
  }
  if(min_cost[n]==INF){
    cout<<"error"<<endl;
  }else{
    cout<<min_cost[n]<<endl;
  }
  return(0);
}

ステータス

項目	データ
問題	1257 - ダイクストラ大好き厨とコーナーテストケース
ユーザー名	ei1630
投稿日時	2020-01-13 04:59:48
言語	C++17
状態	Accepted
得点	5
ソースコード長	1002 Byte
最大実行時間	157 ms
最大メモリ使用量	9884 KB

セット

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

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
corner_input.txt	AC	144 ms	9804 KB	1
input01.txt	AC	157 ms	9884 KB	1
input02.txt	AC	96 ms	7236 KB	1
input03.txt	AC	99 ms	6804 KB	1
input04.txt	AC	126 ms	8212 KB	1
input05.txt	AC	113 ms	8248 KB	1
sample_input.txt	AC	23 ms	2880 KB	1