Submission #1083594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083594		knot222	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	284 ms	32296 KiB

commuter_pass

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#define ll long long int
const ll high = 4e18;
int visited1[200005];
int visited2[200005];
int visited3[200005];
int vv[200005];
ll disU[200005];
ll disV[200005];
ll disS[200005];
ll dp1[200005];
ll dp2[200005];
vector<vector<pair<ll,ll>>> p(200005);
ll ans = 999999999;
void dfs(int nn){
    if(vv[nn]) {
        return;
    }
    vv[nn] = 1;
    dp1[nn] = disU[nn];
    dp2[nn] = disV[nn];
    for (int i=0;i<p[nn].size();i++) {
        if (disS[p[nn][i].second]+p[nn][i].first==disS[nn]) {
            dfs(p[nn][i].second);
            dp1[nn]=min(dp1[nn],dp1[p[nn][i].second]);
            dp2[nn]=min(dp2[nn],dp2[p[nn][i].second]);            
        }
    }
    ans=min(ans,dp1[nn]+disV[nn]);
    ans=min(ans,dp2[nn]+disU[nn]);
}
int main()
{
    ll N,M,S,T,U,V;
    cin >> N >> M >> S >> T >> U >> V;
    for (int i=0;i<M;i++) {
        ll t1,t2,t3;
        cin>>t1>>t2>>t3;
        p[t1].push_back(make_pair(t3,t2));
        p[t2].push_back(make_pair(t3,t1));
    }
    for (int i=0;i<=N;i++) {
        disU[i] = high;
        disV[i] = high;
        disS[i] = high;
    }
    priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq1;
    pq1.push(make_pair(0,U));
    disU[U] = 0;
    while (!pq1.empty()) {
        auto m = pq1.top();
        ll now = m.second;
        ll weight = m.first;
        pq1.pop();
        if (visited1[now]) {
            continue;
        }
        visited1[now] = 1;
        for (int i=0;i<p[now].size();i++) {
            if (disU[p[now][i].second] > disU[now] + p[now][i].first) {
                disU[p[now][i].second] = disU[now] + p[now][i].first;
                pq1.push(make_pair(disU[p[now][i].second], p[now][i].second));
            }
        }
    }
    priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq2;
    pq2.push(make_pair(0,V));
    disV[V] = 0;
    while (!pq2.empty()) {
        auto m = pq2.top();
        ll now = m.second;
        ll weight = m.first;
        pq2.pop();
        if (visited2[now]) {
            continue;
        }
        visited2[now] = 1;
        for (int i=0;i<p[now].size();i++) {
            if (disV[p[now][i].second] > disV[now] + p[now][i].first) {
                disV[p[now][i].second] = disV[now] + p[now][i].first;
                pq2.push(make_pair(disV[p[now][i].second], p[now][i].second));
            }
        }
    }
    priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq3;
    pq3.push(make_pair(0,S));
    disS[S] = 0;
    while (!pq3.empty()) {
        auto m = pq3.top();
        ll now = m.second;
        ll weight = m.first;
        pq3.pop();
        if (visited3[now]) {
            continue;
        }
        visited3[now] = 1;
        for (int i=0;i<p[now].size();i++) {
            if (disS[p[now][i].second] > disS[now] + p[now][i].first) {
                disS[p[now][i].second] = disS[now] + p[now][i].first;
                pq3.push(make_pair(disS[p[now][i].second], p[now][i].second));
            }
        }
    }

    ans = disU[V];
    dfs(T);
    cout << ans;
    /*
    for (int i=1;i<=N;i++) {
        cout << disU[i] << ' ';
    }
    cout << endl;
        for (int i=1;i<=N;i++) {
        cout << disV[i] << ' ';
    }
    cout << endl;
    for (int i=1;i<=N;i++) {
        cout << disS[i] << ' ';
    }*/
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dfs(int)':
commuter_pass.cpp:24:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for (int i=0;i<p[nn].size();i++) {
      |                  ~^~~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:61:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for (int i=0;i<p[now].size();i++) {
      |                      ~^~~~~~~~~~~~~~
commuter_pass.cpp:55:12: warning: unused variable 'weight' [-Wunused-variable]
   55 |         ll weight = m.first;
      |            ^~~~~~
commuter_pass.cpp:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for (int i=0;i<p[now].size();i++) {
      |                      ~^~~~~~~~~~~~~~
commuter_pass.cpp:74:12: warning: unused variable 'weight' [-Wunused-variable]
   74 |         ll weight = m.first;
      |            ^~~~~~
commuter_pass.cpp:99:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         for (int i=0;i<p[now].size();i++) {
      |                      ~^~~~~~~~~~~~~~
commuter_pass.cpp:93:12: warning: unused variable 'weight' [-Wunused-variable]
   93 |         ll weight = m.first;
      |            ^~~~~~

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