Submission #1216612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216612		LmaoLmao	Robot (JOI21_ho_t4)	C++20	0 / 100	219 ms	38128 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>;
 
const int N = 1e6+5;
const int INF = 1e9;
const int mod = 1e9+7;

vector<aa> adj[100005];
map<int,int> mp[100005]; 
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;
    }
    for(int i=2;i<=n;i++) {
        d[i]=1e18;
    }
    priority_queue<ii,vector<ii>,greater<ii>> q;
    q.push({0,1});
    while(!q.empty()) {
        ii u=q.top();
        q.pop();
        if(u.fi>d[u.se]) continue;
        for(aa v:adj[u.se]) {
            v[1]=min(v[1],mp[u.se][v[2]]-v[1]);
            if(d[v[0]]>u.fi+v[1]) {
                q.push({d[v[0]]=u.fi+v[1],v[0]}); 
            }
        }
    }
    if(d[n]==1e18) {
        cout << -1;
        return 0;
    }
    cout << d[n];
    return 0; 
}
/*
██╗░░██╗██╗░░██╗░█████╗░███╗░░██╗░██████╗░              ░██████╗██╗██╗░░░██╗                ░█████╗░██╗░░░██╗████████╗███████╗
██║░██╔╝██║░░██║██╔══██╗████╗░██║██╔════╝░              ██╔════╝██║██║░░░██║                ██╔══██╗██║░░░██║╚══██╔══╝██╔════╝
█████═╝░███████║███████║██╔██╗██║██║░░██╗░              ╚█████╗░██║██║░░░██║                ██║░░╚═╝██║░░░██║░░░██║░░░█████╗░░
██╔═██╗░██╔══██║██╔══██║██║╚████║██║░░╚██╗              ░╚═══██╗██║██║░░░██║                ██║░░██╗██║░░░██║░░░██║░░░██╔══╝░░
██║░╚██╗██║░░██║██║░░██║██║░╚███║╚██████╔╝              ██████╔╝██║╚██████╔╝                ╚█████╔╝╚██████╔╝░░░██║░░░███████╗
╚═╝░░╚═╝╚═╝░░╚═╝╚═╝░░╚═╝╚═╝░░╚══╝░╚═════╝░              ╚═════╝░╚═╝░╚═════╝░                ░╚════╝░░╚═════╝░░░░╚═╝░░░╚══════╝
*/

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