Submission #1216678

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216678		LmaoLmao	Robot (JOI21_ho_t4)	C++20	0 / 100	176 ms	29196 KiB

Main

#include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
 
using ll = long long;
using ii = pair<ll, ll>;
using aa = array<int,3>; 
using aa4 = array<int,4>; 
 
const int N = 1e6+5;
const int INF = 1e9;
const int mod = 1e9+7;

vector<aa> adj[100005];
map<int,int> mp[100005]; 
map<int,int> d[100005];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=m;i++) {
        int u,v,c,w;
        cin >> u >> v >> c >> w;
        adj[u].push_back({v,w,c});
        adj[v].push_back({u,w,c});
        mp[u][c]+=w;
        mp[v][c]+=w;
        d[u][c]=1e18;
        d[v][c]=1e18; 
    }
    for(int i=2;i<=n;i++) {
        d[i][0]=1e18;
    }
    priority_queue<aa,vector<aa>,greater<aa>> q;
    q.push({0,1,0});
    while(!q.empty()) {
        aa u=q.top();
        q.pop();
        if(u[0]>d[u[1]][u[2]]) continue;
        for(aa v:adj[u[1]]) {    
            if(u[2]!=0 &&v[2]!=u[2]) continue;
            int cur=mp[u[1]][v[2]];  
            if(d[v[0]][0]>u[0]+cur-v[1]) {  
                q.push({d[v[0]][0]=u[0]+cur-v[1],v[0],0});  
            } 
            if(u[2]!=0 &&v[2]==u[2]) continue;
            if(d[v[0]][v[2]]>u[0]) { 
                q.push({d[v[0]][v[2]]=u[0],v[0],v[2]});  
            }
            v[1]=min(v[1],cur-v[1]);
            if(d[v[0]][0]>u[0]+v[1]) { 
                q.push({d[v[0]][0]=u[0]+v[1],v[0],v[2]});  
            }
        }
    }
    for(int i=1;i<=n;i++) {
        //cout << d[i][0] << endl;
    }
    if(d[n][0]==1e18) {
        cout << -1;
        return 0;
    }
    cout << d[n][0];
    return 0; 
}
/*
██╗░░██╗██╗░░██╗░█████╗░███╗░░██╗░██████╗░              ░██████╗██╗██╗░░░██╗                ░█████╗░██╗░░░██╗████████╗███████╗
██║░██╔╝██║░░██║██╔══██╗████╗░██║██╔════╝░              ██╔════╝██║██║░░░██║                ██╔══██╗██║░░░██║╚══██╔══╝██╔════╝
█████═╝░███████║███████║██╔██╗██║██║░░██╗░              ╚█████╗░██║██║░░░██║                ██║░░╚═╝██║░░░██║░░░██║░░░█████╗░░
██╔═██╗░██╔══██║██╔══██║██║╚████║██║░░╚██╗              ░╚═══██╗██║██║░░░██║                ██║░░██╗██║░░░██║░░░██║░░░██╔══╝░░
██║░╚██╗██║░░██║██║░░██║██║░╚███║╚██████╔╝              ██████╔╝██║╚██████╔╝                ╚█████╔╝╚██████╔╝░░░██║░░░███████╗
╚═╝░░╚═╝╚═╝░░╚═╝╚═╝░░╚═╝╚═╝░░╚══╝░╚═════╝░              ╚═════╝░╚═╝░╚═════╝░                ░╚════╝░░╚═════╝░░░░╚═╝░░░╚══════╝
*/

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