Submission #44482

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int,int> pii;
vector<pii>edge[100010];
//pair型の片方に{b}を入れる。もう片方に{c}を入れる。配列には{a}を入れる。
int costs[100010];
//その場所に行くまでのコストの合計の最小値
//costs[].1<<30; →　1から行けない
//costs[].それ以外 ← 行ける（最小コスト）
int main(){
int n,m; //{n}は頂点数、{m}は辺数
cin>>n>>m;
for(int i=1;i<=n;i++)costs[i]=1<<30;
//costs[i]の値に1を入れて30左シフト
for(int i=0;i<m;i++){
int a,b,c;
//{a}は今いるノード、{b}は行き先、{c}はコスト
cin>>a>>b>>c; //辺の情報
edge[a].push_back(make_pair(b,c)); //{a}→{b}
edge[b].push_back(make_pair(a,c)); //{b}←{a}
}
//ダイクストラ開始
priority_queue <pii,vector<pii>,greater<pii> > pque;
//一つめは型、二つめは　、三つめは優先度
//piiは一つめにコスト、二つめに行き先を入れる。
pque.push(make_pair(0,1)); //最初にいる所なのでコストは0
while(!pque.empty()){ //{pque}の中が空になるまで
pii now=pque.top(); //取り出す。
int cost=now.first;
int pos=now.second; //今いる所
pque.pop(); //取り出したものを{pque}から消す。
for(int i=0;i<edge[pos].size();i++){
//頂点{pos}にある辺を全て見る。
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<<"NA\n";
else
cout<<costs[n]<<'\n';
return 0;
}

ステータス

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

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
m_in1.txt AC 108 ms 7004 KB
1
r_in1.txt AC 46 ms 3892 KB
1
r_in2.txt AC 34 ms 3804 KB
1
r_in3.txt AC 45 ms 3904 KB
1
r_in4.txt AC 29 ms 3408 KB
1
r_in5.txt AC 42 ms 3980 KB
1
r_in6.txt AC 39 ms 3884 KB
1
r_in7.txt AC 27 ms 3280 KB
1
r_in8.txt AC 30 ms 3408 KB
1
r_in9.txt AC 43 ms 4124 KB
1
r_in10.txt AC 24 ms 3336 KB
1
r_in11.txt AC 36 ms 3668 KB
1
r_in12.txt AC 36 ms 3812 KB
1
r_in13.txt AC 33 ms 3788 KB
1
r_in14.txt AC 37 ms 3824 KB
1
r_in15.txt AC 48 ms 3944 KB
1
r_in16.txt AC 27 ms 3516 KB
1
r_in17.txt AC 28 ms 3680 KB
1
r_in18.txt AC 30 ms 3660 KB
1
r_in19.txt AC 34 ms 3204 KB
1
r_in20.txt AC 41 ms 3452 KB
1
r_in21.txt AC 22 ms 3240 KB
1
r_in22.txt AC 31 ms 3324 KB
1
r_in23.txt AC 29 ms 3320 KB
1
r_in24.txt AC 36 ms 3252 KB
1
r_in25.txt AC 28 ms 3500 KB
1
r_in26.txt AC 39 ms 3536 KB
1
r_in27.txt AC 42 ms 3592 KB
1
r_in28.txt AC 43 ms 3632 KB
1
r_in29.txt AC 43 ms 3732 KB
1
r_in30.txt AC 32 ms 3776 KB
1