Submission #1039703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039703		doducanh	Robot (JOI21_ho_t4)	C++14	100 / 100	825 ms	99612 KiB

Main

///breaker
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define ii pair<int,int>
#define iii pair<int,ii>
#define mp make_pair
const int maxn=1e5+7;
const int inf=1e18+7;
struct canh{
    int v,c,p;
};
map<int,vector<ii>>g[maxn];
vector<canh>adj[maxn];
int dp1[maxn];
map<int,int>psum[maxn];
map<int,int>dp2[maxn];
void sol(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)dp1[i]=inf;
    for(int i=1;i<=m;i++){
        int u,v,c,p;
        cin>>u>>v>>c>>p;
        adj[u].push_back({v,c,p});
        adj[v].push_back({u,c,p});
        psum[u][c]+=p;
        g[u][c].push_back({v,p});
        psum[v][c]+=p;
        g[v][c].push_back({u,p});
    }
    priority_queue<iii,vector<iii>,greater<iii>>q;
    q.push(make_pair(0,make_pair(1,0)));
    dp1[1]=0;
    while(q.size()){
        int u=q.top().se.fi;
        int c=q.top().se.se;
        int du=q.top().fi;
        q.pop();
        if(c==0){if(du>dp1[u])continue;}
        else{if(dp2[u][c]<du)continue;}
        if(c){
            for(auto p:g[u][c]){
                int v=p.fi;
                int w=p.se;
                int case1=psum[u][c]-w;
                if(case1+du<dp1[v]){
                    dp1[v]=case1+du;
                    q.push(mp(du+case1,mp(v,0)));
                }
            }
        }
        else{
            for(auto [v,c,w]:adj[u]){
                int case1=du+psum[u][c]-w;
                if(case1<dp1[v]){
                    dp1[v]=case1;
                    q.push(mp(case1,mp(v,0)));
                }
                int case2=du+w;
                if(case2<dp1[v]){
                    dp1[v]=case2;
                    q.push(mp(case2,mp(v,0)));
                }
                int case3=du;
                if(!dp2[v].count(c)||dp2[v][c]>du){
                    dp2[v][c]=case3;
                    q.push(mp(case3,mp(v,c)));
                }
            }
        }
    }
    cout<<(dp1[n]==inf?-1:dp1[n]);
}
main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    while(t--){
        sol();
    }
    // you should actually read the stuff at the bottom
    return 0;
}
/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

Compilation message (stderr)

Main.cpp: In function 'void sol()':
Main.cpp:56:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |             for(auto [v,c,w]:adj[u]){
      |                      ^
Main.cpp: At global scope:
Main.cpp:77:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   77 | main()
      | ^~~~

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