Submission #1036065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036065		soncao	Robot (JOI21_ho_t4)	C++17	0 / 100	258 ms	94468 KiB

Main

#include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define ii pair<int,int>
#define lll pair<ll,ll>
#define vi vector<int>
#define vvi vector<vector<int>>
struct P{
    int v,c,w;
};
vector<P>a[1000001];
map<int,int>mp[1000001];
ll d[1000001];
int n,m;
void djk()
{
    priority_queue<lll>q;
    q.push({0,1});
    d[1]=0;
    for(int i=2;i<=n;i++){
        d[i]=1e18;
    }
    while(q.size()){
        int u=q.top().second,wu=-q.top().first;
        q.pop();
        for(P it:a[u]){
            int v=it.v,c=it.c,w=it.w;
            if(mp[u][c]==1){
                if(wu<d[v]){
                    d[v]=wu;
                    q.push({-wu,v});
                }
            }else{
                if(wu+1LL*w<d[v]){
                    d[v]=wu+1LL*w;
                    q.push({-(wu+1LL*w),v});
                }
            }
        }
    }
    if(d[n]==1e18)cout<<-1;
    else cout<<d[n];
}
void sc()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,c,w;cin>>u>>v>>c>>w;
        a[u].push_back({v,c,w});
        a[v].push_back({u,c,w});
        mp[u][c]+=1;
        mp[v][c]+=1;
    }
    djk();
}
int main()
{
   // freopen("robot1.inp","w",stdout);
    //freopen("robot1.out","w",stdout);
    ios_base :: sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;
    sc() ;
    return 0 ; ///sc
}

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