제출 #1251735

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251735		mngoc._.	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	277 ms	28248 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FOD(i, r, l) for (int i = (r), _l = (l); i >= _l; i--)
#define pii pair<int,int>
#define endl '\n'
#define pb push_back
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define Konosuba tuple<int , int , int, int>
 
const int N = 3e5 + 5;
const int MOD = 1e9 + 7;
const int block = 320;
const int LOG = 30;
const int MAXN = 1e6 + 5;
const int INF = 1e18;

template<class A, class B>
bool umin(A& var, const B& val){ return (val < var) ? (var = val, true) : false; }
template<class A, class B>
bool umax(A& var, const B& val){ return (var < val) ? (var = val, true) : false; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class X, class Y> int random(const int& l, const int& r) {
    return uniform_int_distribution<int>(l,r)(rng);
}

int dist1[N];
int dist2[N];
int dp[2][N];
int dist3[N];
int res = INF;
int n , m , a , b , c , d;
vector<pii> adj[N];



void dijikstra(int Megumin , int dist[]){
    FOR(i , 1 , n){
        dist[i] = INF;
    }
    dist[Megumin] = 0;
    priority_queue<pii , vector<pii> , greater<pii>> pq;
    pq.push({dist[Megumin] , Megumin});
    while(pq.size()){
        int u = pq.top().second;
        int val = pq.top().first;
        pq.pop();
        if(val > dist[u]) continue;
        for(auto v : adj[u]){
            if(dist[v.first] > dist[u] + v.second){
                dist[v.first] = dist[u] + v.second;
                pq.push({dist[v.first] , v.first});
            }
        }
    }

}


void KonoDijikstra(int be , int ed){
     FOR(i , 0 , 1){
        FOR(j , 1 , n){
            dp[i][j] = INF;
            dist3[j] = INF;
        }
     }
     priority_queue<Konosuba , vector<Konosuba> , greater<Konosuba>> pq;
     dist3[be] = 0;
     dp[0][be] = dist1[be];
     dp[1][be] = dist2[be];
     pq.push({0 , be , dist1[be] , dist2[be]});
     while(pq.size()){
        int val = get<0>(pq.top());
        int u = get<1>(pq.top());
        int c1 = get<2>(pq.top());
        int c2 = get<3>(pq.top());
        pq.pop();
        if(val > dist3[u]) continue;
        for(auto v : adj[u]){
            int ndist = dist3[u] + v.second;
            int ndp1 = (c1 < dist1[v.first] ? c1 : dist1[v.first]);
            int ndp2 = (c2 < dist2[v.first] ? c2 : dist2[v.first]);
            if(dist3[v.first] > dist3[u] + v.second){
                dist3[v.first] = ndist;
                dp[0][v.first] = ndp1;
                dp[1][v.first] = ndp2;
                pq.push({dist3[v.first] , v.first , dp[0][v.first] , dp[1][v.first]});
            }
            else if(dist3[v.first] == dist3[u] + v.second && ndp1 + ndp2 < dp[0][v.first] + dp[1][v.first]){
                dist3[v.first] = ndist;
                dp[0][v.first] = ndp1;
                dp[1][v.first] = ndp2;
                pq.push({dist3[v.first] , v.first , dp[0][v.first] , dp[1][v.first]});
            }
        }

     }
     res = min(res , dp[0][ed] + dp[1][ed]);
}





void solve(void){
    cin >> n >> m >> a >> b >> c >> d;
    FOR(i , 1 , m){
        int u , v , w;
        cin >> u >> v >> w;
        adj[u].push_back({v , w});
        adj[v].push_back({u , w});
    }
    dijikstra(c , dist1);
    dijikstra(d , dist2);
    res = dist1[d];
     KonoDijikstra(a , b);
     KonoDijikstra(b , a);
    cout << res;


}



signed main(void) {
    if (fopen("TASK.INP", "r")) {
        freopen("TASK.INP", "r", stdin);
        freopen("TASK.OUT", "w", stdout);
    } 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int testCase = 1; //cin >> testCase;
    FOR(i , 1 , testCase){
        solve();
    }

    cerr << "Time elapsed: " << TIME << "s.\n";
    return (0);
}

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

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

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