Submission #1102720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102720		ttamx	Robot (JOI21_ho_t4)	C++17	34 / 100	3060 ms	126564 KiB

Main

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

const int N=100'005;
const int M=200'005;
const ll INF=LLONG_MAX/2;

int n,m;
int eu[M],ev[M],ec[M],ew[M];
vector<pair<int,int>> adj[N];
map<int,vector<pair<int,int>>> adjc[N];
map<int,ll> sum[N];
map<int,array<ll,2>> dp[N];
map<int,array<bool,2>> vis[N];
bool vis2[N];
priority_queue<tuple<ll,int,int,int>,vector<tuple<ll,int,int,int>>,greater<tuple<ll,int,int,int>>> pq;

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;
    for(int i=0;i<m;i++){
        cin >> eu[i] >> ev[i] >> ec[i] >> ew[i];
        adj[eu[i]].emplace_back(ev[i],i);
        adj[ev[i]].emplace_back(eu[i],i);
        adjc[eu[i]][ec[i]].emplace_back(ev[i],i);
        adjc[ev[i]][ec[i]].emplace_back(eu[i],i);
        dp[eu[i]][i]={INF,INF};
        dp[ev[i]][i]={INF,INF};
    }
    for(int u=1;u<=n;u++){
        for(auto [v,i]:adj[u]){
            sum[u][ec[i]]+=ew[i];
        }
    }
    for(auto [v,i]:adj[1]){
        dp[v][i][0]=sum[1][ec[i]]-ew[i];
        dp[v][i][1]=ew[i];
        pq.emplace(dp[v][i][0],v,i,0);
        pq.emplace(dp[v][i][1],v,i,1);
    }
    while(!pq.empty()){
        auto [d,u,i,t]=pq.top();
        pq.pop();
        if(vis[u][i][t])continue;
        vis[u][i][t]=true;
        if(u==n){
            cout << d;
            exit(0);
        }
        if(!vis2[u]){
            vis2[u]=true;
            for(auto [v,j]:adj[u]){
                if(i==j)continue;
                ll d0=d+sum[u][ec[j]]-ew[j]-(t&&ec[i]==ec[j]?ew[i]:0);
                ll d1=d+ew[j];
                if(d0<dp[v][j][0]){
                    dp[v][j][0]=d0;
                    pq.emplace(d0,v,j,0);
                }
                if(d1<dp[v][j][1]){
                    dp[v][j][1]=d1;
                    pq.emplace(d1,v,j,1);
                }
            }
        }
        if(t){
            for(auto [v,j]:adjc[u][ec[i]]){
                ll d0=d+sum[u][ec[j]]-ew[j]-ew[i];
                if(d0<dp[v][j][0]){
                    dp[v][j][0]=d0;
                    pq.emplace(d0,v,j,0);
                }
            }
        }
    }
    cout << -1;
}

• Subtask 1: 34 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42