Submission #1451827


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--;
    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) {
        if (u == s || u == t) continue;
        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 2041 Byte
Status WA
Exec Time 344 ms
Memory 896 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 50
WA × 4
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 72 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 344 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 275 ms 896 KB
random-04-0364 AC 16 ms 896 KB
random-05-0053 AC 2 ms 384 KB
random-06-0613 AC 25 ms 896 KB
random-07-0729 AC 109 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 43 ms 512 KB
random-12-0115 AC 4 ms 384 KB
random-13-0260 AC 20 ms 512 KB
random-14-0033 AC 1 ms 256 KB
random-15-0579 WA 4 ms 384 KB
random-16-0713 AC 77 ms 896 KB
random-17-0336 AC 11 ms 896 KB
random-18-0297 AC 7 ms 896 KB
random-19-0826 AC 237 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 12 ms 896 KB
random-26-0043 AC 2 ms 384 KB
random-27-0348 AC 9 ms 896 KB
random-28-0756 AC 122 ms 896 KB
random-29-0647 AC 168 ms 896 KB
random-30-0854 AC 38 ms 896 KB
random-31-0554 AC 49 ms 896 KB
random-32-0632 AC 27 ms 640 KB
random-33-0776 AC 36 ms 896 KB
random-34-0165 AC 15 ms 896 KB
random-35-0695 AC 3 ms 512 KB
random-36-0136 AC 8 ms 640 KB
random-37-0831 AC 99 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