Submission #00133

ソースコード

?
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
#define fr first
#define sc second
#define pb(a) push_back(a)
using namespace std;
typedef pair<int, int> P; //to, from
typedef pair<int, P> PP; //cost, P
vector<P> v[10000]; // cost, to
int N, M, S, G; // 凌堯�凌HV个泙譴睡、里
int costs[10000]; // dij僉路里忙
int froms[10000]; // dij僉路竜録 <- ->
int route[10000], rn; // 路粒納
int solve(){
int lc = 0, time = 0, pol[10000] = {0};
for(int i = 1; i < rn; i++){
pol[i] = costs[route[i-1]] - costs[route[i]] + time;
time = pol[i];
}
for(int i = 1; i < rn; i++) lc += (pol[i]*2);
return lc;
}
bool dij(){
bool used[10000] = {0};
for(int i = 0; i < 10000; i++) costs[i] = INT_MAX;
priority_queue<PP, vector<PP>, greater<PP> > que;
que.push(PP(0, P(S, -1)));
while(!que.empty()){
//int rqjrjh = 0;
//cout << rqjrjh++ << endl;
PP pp = que.top(); que.pop();
int cost = pp.fr, now = pp.sc.fr, from = pp.sc.sc;
if(cost < costs[now]){
costs[now] = cost;
froms[now] = from;
}
if(now == G){
used[now] = 1;
continue;
}
for(int i = 0; i < v[now].size(); i++){
int nc = v[now][i].fr + cost, nx = v[now][i].sc;
if(!used[nx]) que.push(PP(nc, P(nx, now)));
}
used[now] = 1;
}
if(!used[G]) return 0;
rn = 0;
int r = G;
while(r != -1){
route[rn] = r;
rn++;
r = froms[r];
}
return 1;
}
int main(){
cin >> N >> M >> S >> G;
S--; G--;
for(int i = 0; i < M; i++){
int a, b, c;
cin >> a >> b >> c;
a--; b--;
v[a].pb(P(c, b));
v[b].pb(P(c, a));
}
//cout << "se" << endl;
if(!dij()) cout << "Homoed." << endl;
else cout << solve() << " " << costs[G] << endl;
}

ステータス

項目 データ
問題 0008 - Mission ： ホモへの堕落を回避せよ
ユーザー名 ei1409
投稿日時 2016-05-14 15:53:07
言語 C++11
状態 Accepted
得点 14
ソースコード長 1798 Byte
最大実行時間 23 ms
最大メモリ使用量 1500 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1.txt AC 15 ms 860 KB
1
in2.txt AC 14 ms 972 KB
1
in3.txt AC 13 ms 940 KB
1
in4.txt AC 12 ms 1032 KB
1
in5.txt AC 18 ms 1328 KB
1
in6.txt AC 16 ms 1500 KB
1
in7.txt AC 15 ms 1276 KB
1
in8.txt AC 15 ms 1408 KB
1
in9.txt AC 13 ms 964 KB
1
in10.txt AC 12 ms 1040 KB
1
in11.txt AC 12 ms 884 KB
1
in12.txt AC 15 ms 848 KB
1
in13.txt AC 12 ms 992 KB
1
in14.txt AC 16 ms 956 KB
1
in15.txt AC 17 ms 1052 KB
1
in16.txt AC 23 ms 1140 KB
1
in17.txt AC 14 ms 1132 KB
1
in18.txt AC 18 ms 1284 KB
1
in19.txt AC 18 ms 1476 KB
1
in20.txt AC 14 ms 1024 KB
1