Submission #638767

#	Time	Username	Problem	Language	Result	Execution time	Memory
638767		victor_gao	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	515 ms	65980 KiB

commuter_pass

//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 100015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int n,m,s,t,u,v,dis[N][3][2],path[N],can[N];
// 0 非路上 1 順 2 逆 
vector<pii>g[N];
vector<pair<pii,int> >edge,ng[N];
void dijkstra1(){
    priority_queue<pii,vector<pii>,greater<pii> >pq;
    for (int i=1;i<=n;i++)
        path[i]=1e18;
    path[s]=0;
    pq.push({path[s],s});
    while (!pq.empty()){
        pii np=pq.top(); pq.pop();
        if (np.x!=path[np.y]) continue;
        for (auto i:g[np.y]){
            if (path[i.x]>np.x+i.y){
                path[i.x]=np.x+i.y;
                pq.push({path[i.x],i.x});
            }
        }
    }
    queue<int>q;
    can[t]=1;
    q.push(t);
    while (!q.empty()){
        int np=q.front(); q.pop();
        for (auto i:g[np]){
            if (!can[i.x]&&path[i.x]+i.y==path[np]){
                can[i.x]=1;
                q.push(i.x);
            }
        }
    }
}
void build(){
    for (auto i:edge){
        if (can[i.x.x]&&can[i.x.y]){
            if (path[i.x.x]+i.y==path[i.x.y]){
                ng[i.x.x].push_back({{i.x.y,0},1});
                ng[i.x.y].push_back({{i.x.x,0},2});
            }
            else if (path[i.x.y]+i.y==path[i.x.x]){
                ng[i.x.y].push_back({{i.x.x,0},1});
                ng[i.x.x].push_back({{i.x.y,0},2});
            }
        }
        ng[i.x.x].push_back({{i.x.y,i.y},0});
        ng[i.x.y].push_back({{i.x.x,i.y},0});
    }
}
struct Node{
    int d,p,go,k;
    Node(int a,int b,int c,int d):d(a),p(b),go(c),k(d){}
    bool operator<(const Node a)const{ return d>a.d; }
};
priority_queue<Node>pq;
void relax(Node now,pair<pii,int>e){
    Node ok=Node(0,0,0,0);
    if (e.y==0){
        if (now.d+e.x.y<dis[e.x.x][now.go][0]){
            dis[e.x.x][now.go][0]=now.d+e.x.y;
            ok=Node(now.d+e.x.y,e.x.x,now.go,0);
        }
        else return;
    }
    else {
        if (now.go==e.y){
            if (!now.k) return;
            else if (now.d+e.x.y<dis[e.x.x][now.go][1]){
                dis[e.x.x][now.go][1]=now.d+e.x.y;
                ok=Node(now.d+e.x.y,e.x.x,now.go,1);
            }
            else return;
        }
        else {
            if (now.go==0){
                if (now.d+e.x.y<dis[e.x.x][e.y][1]){
                    dis[e.x.x][e.y][1]=now.d+e.x.y;
                    ok=Node(now.d+e.x.y,e.x.x,e.y,1);
                }
                else return;
            }
            else return;
        }
    }
    pq.push(ok);
}
void dijkstra2(){    
    for (int i=1;i<=n;i++){
        for (int j=0;j<3;j++){
            for (int k=0;k<2;k++)
                dis[i][j][k]=1e18;
        }
    }
    dis[u][0][0]=0;
    pq.push(Node(0,u,0,0));
    while (!pq.empty()){
        Node np=pq.top(); pq.pop();
      //  cout<<np.p<<" "<<np.go<<" "<<np.k<<" "<<np.d<<'\n';
        if (np.d!=dis[np.p][np.go][np.k]) continue;
        for (auto i:ng[np.p])
            relax(np,i);
    }
}
signed main(){
    fast
    cin>>n>>m>>s>>t>>u>>v;
    for (int i=1;i<=m;i++){
        int a,b,c; cin>>a>>b>>c;
        edge.push_back({{a,b},c});
        g[a].push_back({b,c});
        g[b].push_back({a,c});
    }
    dijkstra1();
    build();
    dijkstra2();
    cout<<min({dis[v][0][0],dis[v][0][1],dis[v][1][0],dis[v][1][1],dis[v][2][0],dis[v][2][1]})<<'\n';
}

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