제출 #1319011

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1319011		keeray	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	192 ms	20140 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define FOR(i,a,b) for(int i = (a), _b = b;i <= _b; i++)
#define FORD(i,a,b) for(int i = (a), _b = b;i >= _b; i--)
#define pb push_back
#define all(x) x.begin(),x.end()
#define task "path"
#define mp make_pair
template<class x,class y>
    bool minimize(x &a,const y &b){
        if(a > b){
            a = b;
            return true;
        }else return false;
    }
template<class x,class y>
    bool maximize(x &a,const y &b){
        if(a < b){
            a = b;
            return true;
        }else return false;
    }
typedef pair<int,int> pii;
constexpr int MAXN=1e6,MOD=1e9+7,INF=1e18;
int n,m,s,t,u,v,k,l,r,ans,res;
int dist[3][MAXN];
vector<pii> adj[MAXN];
void dij1(int i,int type){
    FOR(j,1,n) dist[type][j] = INF;
    dist[type][i] = 0;
    priority_queue<pii, vector<pii> > pq;
    pq.push({0,i});
    while(!pq.empty()){
        int w = -pq.top().fi;
        int v = pq.top().se;
        pq.pop();
        if(dist[type][v] != w) continue;
        for(pii u : adj[v]){
            if(dist[type][u.fi] > w + u.se){
                dist[type][u.fi] = w + u.se;
                pq.push(mp(-dist[type][u.fi],u.fi));
            }
        }
    }
}
void dij2(int st,int e){
    vector<int> dp(n+1,INF);
    vector<int> miu(n+1,INF);
    vector<int> miv(n+1,INF);
    dp[st] = 0;
    miu[st] = dist[1][st];
    miv[st] = dist[2][st];
    priority_queue<pii, vector<pii> > pq;
    pq.push(mp(0,st));
    while(!pq.empty()){
        int w = -pq.top().fi;
        int v = pq.top().se;
        pq.pop();
        if(dp[v] != w) continue;
        for(pii u : adj[v]){
            int newu = min(miu[v], dist[1][u.fi]);
            int newv = min(miv[v], dist[2][u.fi]);
            if(dp[u.fi] > w + u.se){
                dp[u.fi] = w + u.se;
                miu[u.fi] = newu;
                miv[u.fi] = newv;
                pq.push(mp(-dp[u.fi],u.fi));
            }else if(dp[u.fi] == w + u.se){
                if(miu[u.fi] + miv[u.fi] > newu + newv){
                    miu[u.fi] = newu;
                    miv[u.fi] = newv;
                    pq.push(mp(-dp[u.fi],u.fi));
                }
            }
            if(dp[e]!=INF)
                minimize(ans,miu[e]+miv[e]);
        }
    }
}
int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    cin >> n >> m;
    cin >> s >> t >> u >> v;
    FOR(i,1,m){
        int u,v,w;
        cin >> u >> v >> w;
        adj[u].pb(mp(v,w));
        adj[v].pb(mp(u,w));
    }
    dij1(u,1);
    dij1(v,2);
    ans = dist[1][v];
    dij2(s,t);
    dij2(t,s);
    cout << ans;
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

commuter_pass.cpp: In function 'int32_t main()':
commuter_pass.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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