Submission #534237

#	Time	Username	Problem	Language	Result	Execution time	Memory
534237		Biaz	Robot (JOI21_ho_t4)	C++17	0 / 100	141 ms	19952 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fi first
#define se second
#define X first
#define Y second
#define ist insert
#define pii pair<int,int>
typedef long long ll;

using namespace std;
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
const int INF=170000000000000;//2147483647;
const int MOD=998244353;//1000000007;
const int N=100005;

struct I{
    int u,c,p;
};
int n,m;
vector<I> e[N];
int d[N];
priority_queue<pii,vector<pii>,greater<pii>> pq;
map<int,int> mp[N];
void dij(){
    fill(d,d+N,INF);
    d[1]=0;
    pq.push({0,1});
    while (pq.size()){
        auto [w,v]=pq.top();pq.pop();
        if (d[v]<w) continue;
        for (auto [u,c,p]:e[v]){
            if (d[u]>(mp[v][c]-1)+w){
                d[u]=(mp[v][c]-1)+w;
                pq.push({d[u],u});
            }
        }
    }
    if (d[n]==INF) cout <<-1;
    else cout <<d[n];
}
void sol(){
    cin >>n>>m;
    for (int i=0,u,v,c,p;i<m;i++){
       cin >>u>>v>>c>>p;
       e[u].pb({v,c,p});
       e[v].pb({u,c,p});
       mp[u][c]++;
       mp[v][c]++;
    }
    dij();
}
signed main()
{
    int _=1;
    //cin >>_;
    while (_--) sol();
    return 0;
}

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