제출 #1268100

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268100		sean503	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	328 ms	27188 KiB

commuter_pass

#include<iostream>
#include<vector>
#include<cstdlib> 
#include<string>
#include<algorithm>
#include<set>
#include<math.h>
#include<map>
#include<deque>
#include<unordered_map>
#include<iomanip>
#include<queue>
#include<array>
#include<climits>
#include<cstring>
#include<unordered_set>
#include<cstdint>
#include<typeinfo>
#include <random>
using namespace std;
#define int long long
const int MAX = 999999999999999LL;
vector<vector<pair<int,int>>> adj;
vector<int> len1;
vector<int> len2;
vector<int> val;
int n,m;
void func(int fx, int ch){
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push({0,fx});
    while(!pq.empty()){
        int y = pq.top().first;
        int x = pq.top().second;
        pq.pop();
        if(ch == 1 && len1[x] <= y || ch == 2 && len2[x] <= y){
            continue;
        }
        if(ch == 1){
            len1[x] = y;
        }else{
            len2[x] = y;
        }
        for(int i = 0; i<adj[x].size(); i++){
            pq.push({adj[x][i].second + y,adj[x][i].first});
        }
    }
}
int func2(int cx, int cy){
    priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>> pq;
    vector<pair<int,int>> v(n+1,{MAX,MAX});
    vector<bool> vis(n+1,false);
    pq.push({0,{cx,0}});
    while(!pq.empty()){
        int node = pq.top().second.first;
        int prev = pq.top().second.second;
        int cost = pq.top().first;
        pq.pop();
        if(val[node] < cost){
            continue;
        }
        if(val[node] == cost && vis[node]){
            if(min(v[prev].first,len1[node]) + min(v[prev].second,len2[node]) > v[node].first + v[node].second){
                continue;
            }
            v[node].first = min(v[prev].first,len1[node]);
            v[node].second = min(v[prev].second,len2[node]);
            continue;
        }
        vis[node] = true;
        v[node].first = min(len1[node],v[prev].first);
        v[node].second = min(len2[node],v[prev].second);
        val[node] = cost;
        for(int i = 0; i<adj[node].size(); i++){
            pq.push({cost+adj[node][i].second,{adj[node][i].first,node}});
        }
    }
    return v[cy].first+v[cy].second;
}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>m;
    adj.resize(n+1);
    len1.assign(n+1,MAX);
    len2.assign(n+1,MAX);
    val.assign(n+1,MAX);
    int cx,cy,lx,ly;
    cin>>cx>>cy>>lx>>ly;
    for(int i = 0; i<m; i++){
        int x,y,z;
        cin>>x>>y>>z;
        adj[x].push_back({y,z});
        adj[y].push_back({x,z});
    }
    func(lx,1);
    func(ly,2);
    int ans = len1[ly];
    ans = min(func2(cx,cy),ans);
    ans = min(func2(cy,cx),ans);
    cout<<ans;
}

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