Submission #987660

#	Time	Username	Problem	Language	Result	Execution time	Memory
987660		doducanh	Robot (JOI21_ho_t4)	C++14	100 / 100	1120 ms	87764 KiB

Main

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define ll long long
#define iii pair<ll,pair<int,int>>
#define fi first
#define se second
struct duongdi
{
    int to,c;
    ll p;
};
const int maxn=1e5+7;
const ll maxx=1e18+7;
map<int,ll>psum[maxn];
map<int,ll>dp2[maxn];
map<int,vector<duongdi>>graph[maxn];
ll dp[maxn];
int n,m;
main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,c,w;
        cin>>x>>y>>c>>w;
        graph[x][c].push_back({y,c,w});
        graph[y][c].push_back({x,c,w});
        psum[x][c]+=w;
        psum[y][c]+=w;
    }
    for(int i=1;i<=n;i++){
        dp[i]=maxx;
    }
    priority_queue<iii,vector<iii>,greater<iii>>q;
    dp[1]=0;
    q.push(make_pair(0,make_pair(1,0)));
    while(q.size()){
        int u=q.top().se.fi;
        int du=q.top().fi;
        int c=q.top().se.se;
        q.pop();
//        cout<<u<<" "<<du<<" "<<c<<"\n";
        if(c){
            if(dp2[u][c]!=du)continue;
            for(auto p:graph[u][c]){
                ll case1=psum[u][c]-p.p;
                if(case1+du<dp[p.to]){
                    dp[p.to]=case1+du;
                    q.push(make_pair(case1+du,make_pair(p.to,0)));
                }
            }
        }
        else{
            if(du!=dp[u])continue;
            for(auto &cc:graph[u]){
                for(auto p:cc.second){
                    ll case1=psum[u][p.c]-p.p;
                    if(dp[p.to]>case1+du){
                        dp[p.to]=case1+du;
                        q.push(make_pair(case1+du,make_pair(p.to,0)));
                    }
                    ll case2=p.p;
                    if(dp[p.to]>case2+du){
                        dp[p.to]=case2+du;
                        q.push(make_pair(case2+du,make_pair(p.to,0)));
                    }
                    ll case3=du;
                    if(!dp2[p.to].count(p.c)||dp2[p.to][p.c]>case3){
                        dp2[p.to][p.c]=case3;
                        q.push(make_pair(case3,make_pair(p.to,p.c)));
                    }
                }
            }
        }
    }
//    for(int i=1;i<=n;i++)cout<<dp[i]<<" ";
//    cout<<"\n";
    cout<<((dp[n]==maxx)?-1:dp[n]);
    return 0;
}

Compilation message (stderr)

Main.cpp:21:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   21 | main()
      | ^~~~

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