제출 #1338630

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1338630		karn7777	꿈 (IOI13_dreaming)	C++20	18 / 100	63 ms	12028 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
//#define int long long
signed travelTime(int n, int m, int L, int A[], int B[], int T[]) {
    vector<pair<int,int>> path[n+3];
    vector<int> dist(n+3);
    vector<int> d1(n+3);
    vector<int> d2(n+3);
    vector<int> vis(n+3);
    for(int i=0;i<n;i++)dist[i]=d1[i]=d2[i]=INT_MAX;
    for(int i=0;i<m;i++){
        path[A[i]].push_back({B[i],T[i]});
        path[B[i]].push_back({A[i],T[i]});
    }
    priority_queue<int> ans;
    for(int i=0;i<n;i++){
        if(!vis[i]){
            set<int> s;
            priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
            //1st
            pq.push({0,i});
            dist[i]=0;
            while(!pq.empty()){
                auto [W,u]=pq.top();
                pq.pop();
                if(W>dist[u])continue;
                s.insert(u);
                for(auto [v,w]:path[u]){
                    if(dist[v]>dist[u]+w){
                        dist[v]=w+dist[u];
                        pq.push({dist[v],v});
                    }
                }
            }

            //2nd
            int mx=-1,d=1;
            for(auto x:s){
                if(dist[x]>mx){
                    mx=dist[x];
                    d=x;
                }
            }
            pq.push({0,d});
            d1[d]=0;
            while(!pq.empty()){
                auto [W,u]=pq.top();
                pq.pop();
                if(W>d1[u])continue;
                for(auto [v,w]:path[u]){
                    if(d1[v]>d1[u]+w){
                        d1[v]=w+d1[u];
                        pq.push({d1[v],v});
                    }
                }
            }

            //3rd
            mx=-1,d=1;
            for(auto x:s){
                if(d1[x]>mx){
                    mx=d1[x];
                    d=x;
                }
            }
            pq.push({0,d});
            d2[d]=0;
            while(!pq.empty()){
                auto [W,u]=pq.top();
                pq.pop();
                if(W>d2[u])continue;
                for(auto [v,w]:path[u]){
                    if(d2[v]>d2[u]+w){
                        d2[v]=w+d2[u];
                        pq.push({d2[v],v});
                    }
                }
            }
            mx=INT_MAX;
            for(auto x:s){
                vis[x]=true;
                mx=min(mx,max(d1[x],d2[x]));
            }
            ans.push(mx);
        }
    }
    int k=ans.top()-L;
    ans.pop();
    ans.push(k);
    int sum=ans.top();
    ans.pop();
    return sum+ans.top()+2*L;
}
//#undef int

• Subtask 1: 0 / 14
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 18 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23