Submission #1451839
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> plli;
typedef pair<int,pii> pipii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;
#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
const ll mod = 1e9 + 7;
const ll INF = 1<<30;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const double pi = 3.141592653589793;
int n, m;
int s, t;
struct edge{ int to, cost; };
vector<vector<edge>> g(1000 + 3);
vector<ll> dijkstra(int s, int n, vector<vector<edge>>& g){
priority_queue<plli, vector<plli>, greater<plli>> que;
vector<ll> d(n, LLONG_MAX/10); d[s] = 0;
que.push(plli(0, s));
while (!que.empty()){
plli p = que.top();que.pop();
int fr = p.second;
if (d[fr] < p.first) continue;
for (edge e: g[fr]){
if (d[e.to] > d[fr] + e.cost){
d[e.to] = d[fr] + e.cost;
que.push(plli(d[e.to], e.to));
}
}
}
return d;
}
signed main(){
cin.tie(0);
ios::sync_with_stdio(false);
cin >> n >> m;
cin >> s >> t;
s--;t--;
if (s == t || m == 1) {
cout << s + 1 << endl;
exit(0);
}
rep(i, m) {
int x, y, d;
cin >> x >> y >> d;
x--;y--;
g[x].pb({y, d});
g[y].pb({x, d});
}
vector<ll> dist1 = dijkstra(s, n, g);
rep(u, n) {
vector<ll> dist2 = dijkstra(u, n, g);
if (dist1[u] == dist2[t]) {
cout << u + 1 << endl;
exit(0);
}
}
cout << -1 << endl;
}
Submission Info
Submission Time |
|
Task |
C - 身体バランス |
User |
roto_37 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2086 Byte |
Status |
WA |
Exec Time |
347 ms |
Memory |
1024 KB |
Judge Result
Set Name |
All |
Score / Max Score |
0 / 100 |
Status |
|
Set Name |
Test Cases |
All |
00-sample-00, 00-sample-01, corner-case-01, corner-case-02, corner-case-03, largest-00, largest-01, largest-02, largest-03, largest-04, largest-05, random-00-0934, random-01-0457, random-02-0288, random-03-0873, random-04-0364, random-05-0053, random-06-0613, random-07-0729, random-08-0061, random-09-0645, random-10-0095, random-11-0369, random-12-0115, random-13-0260, random-14-0033, random-15-0579, random-16-0713, random-17-0336, random-18-0297, random-19-0826, random-20-0742, random-21-0264, random-22-0507, random-23-0502, random-24-0750, random-25-0721, random-26-0043, random-27-0348, random-28-0756, random-29-0647, random-30-0854, random-31-0554, random-32-0632, random-33-0776, random-34-0165, random-35-0695, random-36-0136, random-37-0831, random-38-0284, random-39-0610, random-40-0421, sample-00, sample-01 |
Case Name |
Status |
Exec Time |
Memory |
00-sample-00 |
AC |
1 ms |
256 KB |
00-sample-01 |
AC |
1 ms |
256 KB |
corner-case-01 |
WA |
1 ms |
256 KB |
corner-case-02 |
WA |
1 ms |
384 KB |
corner-case-03 |
WA |
2 ms |
384 KB |
largest-00 |
AC |
73 ms |
896 KB |
largest-01 |
AC |
4 ms |
896 KB |
largest-02 |
AC |
5 ms |
896 KB |
largest-03 |
AC |
6 ms |
896 KB |
largest-04 |
AC |
347 ms |
896 KB |
largest-05 |
AC |
4 ms |
896 KB |
random-00-0934 |
AC |
14 ms |
896 KB |
random-01-0457 |
AC |
5 ms |
896 KB |
random-02-0288 |
AC |
5 ms |
896 KB |
random-03-0873 |
AC |
279 ms |
896 KB |
random-04-0364 |
AC |
16 ms |
896 KB |
random-05-0053 |
AC |
2 ms |
256 KB |
random-06-0613 |
AC |
25 ms |
896 KB |
random-07-0729 |
AC |
110 ms |
896 KB |
random-08-0061 |
AC |
3 ms |
384 KB |
random-09-0645 |
AC |
4 ms |
896 KB |
random-10-0095 |
AC |
3 ms |
384 KB |
random-11-0369 |
AC |
44 ms |
512 KB |
random-12-0115 |
AC |
4 ms |
384 KB |
random-13-0260 |
AC |
20 ms |
512 KB |
random-14-0033 |
AC |
2 ms |
256 KB |
random-15-0579 |
WA |
4 ms |
384 KB |
random-16-0713 |
AC |
78 ms |
896 KB |
random-17-0336 |
AC |
11 ms |
896 KB |
random-18-0297 |
AC |
7 ms |
896 KB |
random-19-0826 |
AC |
239 ms |
896 KB |
random-20-0742 |
AC |
55 ms |
896 KB |
random-21-0264 |
AC |
16 ms |
896 KB |
random-22-0507 |
AC |
47 ms |
896 KB |
random-23-0502 |
AC |
14 ms |
896 KB |
random-24-0750 |
AC |
15 ms |
896 KB |
random-25-0721 |
AC |
13 ms |
896 KB |
random-26-0043 |
AC |
2 ms |
384 KB |
random-27-0348 |
AC |
9 ms |
896 KB |
random-28-0756 |
AC |
124 ms |
896 KB |
random-29-0647 |
AC |
170 ms |
896 KB |
random-30-0854 |
AC |
38 ms |
896 KB |
random-31-0554 |
AC |
50 ms |
896 KB |
random-32-0632 |
AC |
28 ms |
640 KB |
random-33-0776 |
AC |
37 ms |
1024 KB |
random-34-0165 |
AC |
16 ms |
896 KB |
random-35-0695 |
AC |
4 ms |
512 KB |
random-36-0136 |
AC |
8 ms |
640 KB |
random-37-0831 |
AC |
100 ms |
896 KB |
random-38-0284 |
AC |
13 ms |
896 KB |
random-39-0610 |
AC |
42 ms |
896 KB |
random-40-0421 |
AC |
15 ms |
896 KB |
sample-00 |
AC |
1 ms |
256 KB |
sample-01 |
AC |
1 ms |
256 KB |