제출 #1287726

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287726		ilovewaguri	Commuter Pass (JOI18_commuter_pass)	C++20	16 / 100	197 ms	23792 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
#define NAME "TEST"
#define nl '\n'
#define allofa(x,sz) x,x+sz+1
#define allof(x) x.begin(),x.end()
#define mset(x,val) memset(x,val,sizeof(x))
template<class X,class Y> bool minimize(X &a, Y b){if(a>b){a=b;return true;}return false;};
template<class X,class Y> bool maximize(X &a, Y b){if(a<b){a=b;return true;}return false;};
typedef long long ll;
typedef pair<ll,int> pli;
const ll mod = (long long)1e9+7;
const ll LINF = (long long)1e18;
const int INF = (int)1e9;
const int MAXN = (int)1e5+5;
vector<pli> graph[MAXN];
ll disS[MAXN],disT[MAXN];
ll disU[MAXN],disV[MAXN];
bool visited[MAXN];
array<ll,2> dp[MAXN];
int n,m,s,t,U,V;
ll disST,res;

void ccps() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    if(fopen(NAME".inp","r")) {
        freopen(NAME".inp","r",stdin);
        freopen(NAME".out","w",stdout);
    }
}

void Dijkstra(int src, ll dist[]) {
    fill(allofa(dist,n),LINF);
    priority_queue<pli,vector<pli>,greater<pli>> pq;
    dist[src] = 0;
    pq.push({dist[src],src});
    while(!pq.empty()) {
        int u; ll curDis;
        tie(curDis,u) = pq.top();pq.pop();
        if(curDis>dist[u]) continue;
        for (pli x : graph[u]) {
            int v; ll newDis;
            tie(newDis,v) = x;
            if(minimize(dist[v],newDis+curDis)) {
                pq.push({dist[v],v});
            }
        }
    }
}

void dfs(int u) {
    visited[u]=true;
    dp[u][0]=disU[u];
    dp[u][1]=disV[u];
    for (pli x : graph[u]) {
        int v; ll w;
        tie(w,v) = x;
        if(disS[v]+disT[v]==disST and disS[v]==disS[u]+w) {
            if(!visited[v]) dfs(v);
            minimize(dp[u][0],dp[v][0]);
            minimize(dp[u][1],dp[v][1]);
        }
    }
    minimize(res,dp[u][0]+disV[u]);
    minimize(res,dp[u][1]+disU[u]);
}

signed main() {
    ccps();
    cin >> n >> m >> s >> t >> U >> V;
    for (int i = 1; i<=m; i++) {
        int u,v,w; cin >> u >> v >> w;
        graph[u].push_back({w,v});
        graph[v].push_back({w,u});
    }
    Dijkstra(s,disS);
    Dijkstra(t,disT);
    Dijkstra(U,disU);
    Dijkstra(V,disV);
    disST = disS[t];
    mset(visited,false);
    mset(dp,0x3f3f3f3f);
    res = disU[V];
    dfs(U);
    cout << res;
}

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

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

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