Submission #44478

ソースコード

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int,int> pii;
int costs[100005];
int main(){
  int n,m;
  int a,b,c;
  vector<pii> edge[100005];
  cin>>n>>m;
  for(int i=1;i<=n;i++)costs[i]=1<<30;
  for(int i=1;i<=m;i++){
    cin>>a>>b>>c;
    edge[a].push_back(make_pair(b,c));
    edge[b].push_back(make_pair(a,c));
  }
  priority_queue<pii,vector<pii>,greater<pii> >pQue;//pii<コスト,行き先>とする。
  pQue.push(make_pair(0,1));
  while(!pQue.empty()){
    pii now=pQue.top();
    int cost=now.first;
    int pos=now.second;
    pQue.pop();
    for(int i=0;i<edge[pos].size();i++){//ノードにある辺を全て見る。
      int next=edge[pos][i].first;//posからの行き先
      int next_cost=edge[pos][i].second;
      if(cost+next_cost<costs[next]){
        costs[next]=cost+next_cost;
        pQue.push(make_pair(costs[next],next));
      }
    }
  }
  if(costs[n]!=1<<30){
    cout<<costs[n]<<"\n";
  }else{
    cout<<"NA"<<"\n";
  }
  return 0;
}

ステータス

項目	データ
問題	0431 - 君も始めようダイクストラ大好き厨
ユーザー名	ei1832
投稿日時	2018-10-31 17:49:10
言語	C++
状態	Accepted
得点	1
ソースコード長	1037 Byte
最大実行時間	120 ms
最大メモリ使用量	12644 KB

セット

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

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
m_in1.txt	AC	120 ms	8540 KB	1
r_in1.txt	AC	59 ms	5700 KB	1
r_in2.txt	AC	42 ms	8276 KB	1
r_in3.txt	AC	41 ms	10428 KB	1
r_in4.txt	AC	31 ms	10584 KB	1
r_in5.txt	AC	47 ms	11544 KB	1
r_in6.txt	AC	46 ms	11848 KB	1
r_in7.txt	AC	39 ms	11384 KB	1
r_in8.txt	AC	38 ms	11528 KB	1
r_in9.txt	AC	77 ms	12644 KB	1
r_in10.txt	AC	39 ms	5152 KB	1
r_in11.txt	AC	36 ms	5876 KB	1
r_in12.txt	AC	43 ms	6160 KB	1
r_in13.txt	AC	59 ms	6528 KB	1
r_in14.txt	AC	39 ms	6956 KB	1
r_in15.txt	AC	37 ms	7344 KB	1
r_in16.txt	AC	30 ms	7176 KB	1
r_in17.txt	AC	57 ms	7344 KB	1
r_in18.txt	AC	33 ms	7724 KB	1
r_in19.txt	AC	27 ms	7540 KB	1
r_in20.txt	AC	30 ms	8064 KB	1
r_in21.txt	AC	46 ms	7864 KB	1
r_in22.txt	AC	31 ms	8084 KB	1
r_in23.txt	AC	31 ms	8348 KB	1
r_in24.txt	AC	32 ms	8424 KB	1
r_in25.txt	AC	36 ms	8684 KB	1
r_in26.txt	AC	32 ms	9116 KB	1
r_in27.txt	AC	34 ms	9320 KB	1
r_in28.txt	AC	39 ms	9748 KB	1
r_in29.txt	AC	42 ms	9992 KB	1
r_in30.txt	AC	41 ms	10692 KB	1