Submission #00132

ソースコード

?
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define fr first
#define sc second
#define Rep(i,n) for(int i=0;i<(n);i++)
#define Rrep(i, m, n) for(int i=(m);i<(n);i++)
#define All(v) v.begin(),v.end()
#define Uniq(v) v.erase(unique(All(v)),v.end())
typedef pair<int, int> Pii;
typedef pair<int, Pii> Pip;
typedef pair<string, int> Psi;
typedef vector<int> Vi;
const int INF = (1<<30);
const int dx[]={1,0,-1,0}, dy[]={0,-1,0,1};
int n, m, s, g;
struct Edge {
int to;
int cost;
Edge( int to_, int cost_ ) {
to = to_; cost = cost_;
}
};
vector<Edge> G[800];
int poll_time[800];
/*
void bfs()
{
queue<Pii> q;
q.push( Pii(s, 0) );
while( !q.empty() ) {
Pii p = q.front(); q.pop();
if( poll_time
}
*/
int dij( int st, int gr ) {
priority_queue<Pii, vector<Pii>, greater<Pii> > q;
bool used[800] = {0};
q.push( Pii(0, st) );
while( !q.empty() ) {
Pii p = q.top(); q.pop();
int a = p.fr, b = p.sc;
if( b == gr ) {
return a;
}
if( used[b] ) continue;
used[b] = true;
vector<Edge> e = G[b];
Rep(i, e.size()) {
q.push( Pii(a+e[i].cost, e[i].to) );
}
}
return -1;
}
int all_cost = 0, all_homo = 0;
Pii dij2(int st, int gr) {
priority_queue<Pip, vector<Pip>, greater<Pip> > q;
bool used[800] = {0};
q.push( Pip(all_cost, Pii(all_homo, st)) );
while( !q.empty() ) {
Pip p = q.top(); q.pop();
int a = p.fr, b = p.sc.fr, c = p.sc.sc;
if( c == gr ) {
return Pii(a, b); //a:cost b:homo
}
if( used[c] ) continue;
used[c] = true;
vector<Edge> e = G[c];
Rep(i, e.size()) {
q.push( Pip(a+e[i].cost, Pii(b + a+e[i].cost-poll_time[e[i].to], e[i].to ) ));
}
}
return Pii(-1, -1);
}
int main()
{
fill_n(poll_time, 800, INF);
cin >> n >> m >> s >> g;
s--; g--;
Rep(i, m) {
int a, b, c;
cin >> a >> b >> c;
a--; b--;
G[a].pb( Edge(b, c) );
G[b].pb( Edge(a, c) );
}
poll_time[s] = 0;
Rep(i, n) {
if( i != s ) {
poll_time[i] = dij( s, i );
}
}
Pii ret = dij2(s, g);
int ans = ret.fr;
all_cost = ret.fr; all_homo = ret.sc;
ret = dij2(g, s);
if( ans == -1 && ret.sc == -1 ) cout << "Homoed." << endl;
else cout << ret.sc << " " << ans << endl;
}

ステータス

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

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1.txt AC 98 ms 604 KB
1
in2.txt AC 133 ms 828 KB
1
in3.txt AC 85 ms 624 KB
1
in4.txt AC 106 ms 636 KB
1
in5.txt AC 185 ms 1196 KB
1
in6.txt AC 200 ms 1152 KB
1
in7.txt AC 189 ms 1204 KB
1
in8.txt AC 216 ms 1176 KB
1
in9.txt AC 16 ms 668 KB
1
in10.txt AC 91 ms 836 KB
1
in11.txt AC 89 ms 704 KB
1
in12.txt AC 112 ms 564 KB
1
in13.txt AC 127 ms 892 KB
1
in14.txt AC 132 ms 848 KB
1
in15.txt AC 139 ms 852 KB
1
in16.txt AC 164 ms 900 KB
1
in17.txt AC 159 ms 912 KB
1
in18.txt AC 182 ms 1112 KB
1
in19.txt AC 217 ms 1124 KB
1
in20.txt AC 137 ms 824 KB
1