Submission #114984

#	Time	Username	Problem	Language	Result	Execution time	Memory
114984		Mercenary	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	538 ms	23504 KiB

commuter_pass

#include<bits/stdc++.h>

using namespace std;
#define taskname "A"
#define pb	push_back
#define mp 	make_pair
#ifndef LOCAL
#define cerr if(0)cout
#endif

typedef long double ld;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll,int> lli;

const int maxn = 1e5 + 5;
const ll inf = (ll)1e18;

ll d[4][maxn];
vector<ii> adj[maxn];

void dij(int start , ll d[]){
    priority_queue<lli,vector<lli>,greater<lli>> pq;
    fill_n(d , maxn , inf);
    pq.push(mp(0ll,start));
    d[start] = 0;
    while(!pq.empty()){
        auto u = pq.top();pq.pop();
        if(d[u.second] != u.first)continue;
        for(ii c : adj[u.second]){
            if(d[c.first] > u.first + c.second){
                d[c.first] = u.first + c.second;
                pq.push(mp(d[c.first],c.first));
            }
        }
    }
}

ll dp[maxn][3];
int n , m , s , t , u , v;

void DFS(int u){
//    cout << u << endl;
    if(dp[u][0] != inf)return;
    cerr << u << " ";
    dp[u][0] = min(dp[u][0] , d[0][u]);
    dp[u][1] = min(dp[u][1] , d[1][u]);
    dp[u][2] = d[0][u] + d[1][u];
    for(ii c : adj[u]){
        if(d[2][u] + c.second + d[3][c.first] == d[2][t]){
            DFS(c.first);
            dp[u][2] = min(dp[u][2] , min(dp[u][0],dp[c.first][0]) + dp[u][1]);
            dp[u][2] = min(dp[u][2] , dp[u][0] + min(dp[u][1],dp[c.first][1]));
            dp[u][2] = min(dp[u][2] , dp[c.first][2]);
        }
    }
    for(ii c : adj[u]){
        if(d[2][u] + c.second + d[3][c.first] == d[2][t]){
            dp[u][0] = min(dp[u][0],dp[c.first][0]);
            dp[u][1] = min(dp[u][1],dp[c.first][1]);
        }
    }
}

void enter(){
    cin >> n >> m;
    cin >> s >> t >> u >> v;
    for(int i = 1 ; i <= m ; ++i){
        int u , v , c;cin >> u >> v >> c;
        adj[u].pb(mp(v,c));
        adj[v].pb(mp(u,c));
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    enter();
    dij(u , d[0]);
    dij(v , d[1]);
    dij(s , d[2]);
    dij(t , d[3]);
    fill_n(&dp[0][0],maxn*3,inf);
    DFS(s);
    cout << min(dp[s][2],d[0][v]);
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:80:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:81:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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