Submission #124134

#	Time	Username	Problem	Language	Result	Execution time	Memory
124134		Hideo	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	450 ms	24336 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define vi vector < int >
#define vl vector < ll >
#define pi pair < int, int >
#define pl pair < ll, ll >
#define pii pair < int, pi >
#define vii vector < pi >
#define viii vector < pii >

const int N = 1e5 + 7;
const ll INF = 1e15 + 7;

ll d[5][N], ans;
int n, m;
int s[5], us[N];

vii g[N];

void dijkstra (int id){
    priority_queue < pair < ll, int > > pq;
    pq.push(mk(0LL, s[id]));
    memset(d[id], 0x3f3f3f3f, sizeof d[id]);
    while(!pq.empty()){
        ll dis = -pq.top().fr; int cur = pq.top().sc;
        pq.pop();
        if (d[id][cur] < dis)
            continue;
        d[id][cur] = dis;
        for (pi to : g[cur]){
            if (d[id][to.fr] > dis + to.sc){
                d[id][to.fr] = dis + to.sc;
                pq.push(mk(-d[id][to.fr], to.fr));
            }
        }
    }
}

void dfs (int v, int p = 0, ll rs = INF, ll a = INF, ll b = INF){
    us[v] = 1;
    a = min(a, d[3][v]);
    b = min(b, d[4][v]);
    ll r1 = a + d[4][v];
    r1 = min(r1, b + d[3][v]);
    r1 = min(r1, d[3][v] + d[4][v]);
    rs = min(rs, r1);
    for (pi to : g[v]){
        if (us[to.fr] == 1 || to.fr == p || d[1][v] + to.sc != d[1][to.fr])
            continue;
        if (us[to.fr] == 2){
            ans = min(ans, rs);
            us[v] = 2;
        }
        else
            dfs(to.fr, v, rs, a, b);
    }
    us[p] = max(us[p], us[v]);
}

main (){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= 4; i++)
        scanf("%d", &s[i]);
    for (int i = 1; i <= m; i++){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a].pb(mk(b, c));
        g[b].pb(mk(a, c));
    }
    for (int i = 1; i <= 4; i++)
        dijkstra(i);
    ans = d[3][s[4]];
    us[s[2]] = 2;
    dfs(s[1]);
    printf("%lld", ans);
}

Compilation message (stderr)

commuter_pass.cpp:66:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main (){
       ^
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
commuter_pass.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &s[i]);
         ~~~~~^~~~~~~~~~~~~
commuter_pass.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &a, &b, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45