제출 #1147612

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147612		AlgorithmWarrior	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	242 ms	30124 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

int const MAX=2e5+5;
long long const INF=1e18;
int n,m;
int nod1,nod2;
int nod3,nod4;
struct edge{
    int u,v,w;
}edge[MAX];
struct edg{
    int nod,w;
};
vector<edg>G[MAX];
long long answer;

void read(){
    cin>>n>>m;
    cin>>nod1>>nod2;
    cin>>nod3>>nod4;
    int i;
    for(i=1;i<=m;++i){
        cin>>edge[i].u>>edge[i].v>>edge[i].w;
        auto [u,v,w]=edge[i];
        G[u].push_back({v,w});
        G[v].push_back({u,w});
    }
}

struct sh_path{
    int nod;
    long long dist;
};

class cmp{
public:
    bool operator()(sh_path a,sh_path b){
        return a.dist>b.dist;
    }
};

void dijkstra(int nod,long long path[]){
    int i;
    for(i=1;i<=n;++i)
        path[i]=INF;
    priority_queue<sh_path,vector<sh_path>,cmp>pq;
    pq.push({nod,0});
    path[nod]=0;
    while(!pq.empty()){
        auto [u,dst]=pq.top();
        pq.pop();
        if(path[u]<dst)
            continue;
        for(auto [vec,w] : G[u])
            if(path[vec]>path[u]+w){
                path[vec]=path[u]+w;
                pq.push({vec,path[vec]});
            }
    }
}

long long dist1[MAX],dist2[MAX],dist3[MAX],dist4[MAX];
bool activ[MAX];
vector<int>DAG[MAX];

void build_DAG(){
    long long total_len=dist1[nod2];
    int i;
    for(i=1;i<=n;++i)
        if(dist1[i]+dist2[i]==total_len)
            activ[i]=1;
    for(i=1;i<=m;++i){
        auto [u,v,w]=edge[i];
        if(!activ[u] || !activ[v])
            continue;
        if(dist1[u]>dist1[v])
            swap(u,v);
        if(dist1[u]+w==dist1[v])
            DAG[u].push_back(v);
    }
}

void minself(long long& x,long long val){
    if(x>val)
        x=val;
}

bool viz[MAX];
long long min3[MAX],min4[MAX];

void dfs(int nod){
    min3[nod]=dist3[nod];
    min4[nod]=dist4[nod];
    for(auto fiu : DAG[nod]){
        if(!viz[fiu])
            dfs(fiu);
        minself(min3[nod],min3[fiu]);
        minself(min4[nod],min4[fiu]);
    }
    minself(answer,dist3[nod]+min4[nod]);
    minself(answer,dist4[nod]+min3[nod]);
    viz[nod]=1;
}

int main()
{
    read();
    dijkstra(nod1,dist1);
    dijkstra(nod2,dist2);
    dijkstra(nod3,dist3);
    dijkstra(nod4,dist4);
    build_DAG();
    answer=dist3[nod4];
    dfs(nod1);
    cout<<answer;
    return 0;
}

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