Submission #1268097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268097		sean503	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	332 ms	27220 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;
struct idk{
    int start,end,cost;
};
vector<vector<pair<int,int>>> adj;
vector<int> len1;
vector<int> len2;
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<idk> v(n+1,{MAX,MAX,MAX});
    for(int i = 1; i<=n; i++){
        v[i].start = len1[i];
        v[i].end = len2[i];
    }
    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(v[node].cost < cost){
            continue;
        }
        if(v[node].cost == cost){
            if(v[prev].start + v[node].end > v[node].start + v[node].end){
                continue;
            }
            v[node].start = v[prev].start;
            v[node].end = v[prev].end;
            continue;
        }
        v[node].start = min(v[node].start,v[prev].start);
        v[node].end = min(v[node].end,v[prev].end);
        v[node].cost = 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].start+v[cy].end;
}
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);
    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: 0 / 16
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45