Submission #1036210

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036210		_no_name	Robot (JOI21_ho_t4)	C++17	100 / 100	95 ms	21248 KiB

Main

//Ai_2007
//Make the impossible possible
#include<bits/stdc++.h>
#define ll long long
#define fo(i,m,n) for(int i=m; i<=n; i++)
#define fod(i,m,n) for(int i=m; i>=n; i--)
#define fi first
#define se second
#define Nmax 1000001
#define pb push_back
#define pii pair<int,int>
#define getbit(i,j) ((i>>j)&1)
#define onbit(i,j) (i=(1<<j))
#define offbit(i,j) (i^=(1<<j))
#define pli pair<long long,int>
using namespace std;
const int N=1e5+5;
int n,m,dem[2*N],val[N];
ll dis[N],sum[2*N],save[2*N];
bool vst[N];
struct dl
{
    int u,v,c,p;
};
vector<pair<int,pii>> adj[N];
void dijkstra()
{
    fo(i,1,n) {
        dis[i]=1e18;
        vst[i]=0;
    }
    dis[1]=0;
    priority_queue<pli,vector<pli>,greater<pli>> q;
    q.push({0,1});
    while(!q.empty()){
        int u=q.top().se;
        ll kc=q.top().fi;
//        cout<<u<<" ";
        q.pop();
        if(vst[u]) continue;
        vst[u]=1;
        int cnt=0;
        for(auto it:adj[u]){
            int mau=it.se.fi;
            dem[mau]=0;
            sum[mau]=0;
            save[mau]=1e18;
//            if(mau==col)sum+=cost;
        }
        for(auto it:adj[u]){
            int mau=it.se.fi;
            int cos=it.se.se;
            save[mau]=min(save[mau],dis[it.fi]);
            dem[mau]++;
            sum[mau]+=cos;
            if(dem[mau]==2) cnt++;
//            if(mau==col)sum+=cost;
        }
//        if(cnt==m) continue;
        for(auto it:adj[u]){
            int mau=it.se.fi;
//            if(mau!=col) continue;
            int cost=it.se.se;
            int v=it.fi;
//            if(u==2) cout<<mau<<" ";
//            if(dem[mau]==1) cost=0;
            if(dem[mau]==1){
                if(dis[v] > dis[u]){
                dis[v]=dis[u];
                q.push({dis[v],v});
                }
            }
            else{
                ll cos=1e18;
                if(cnt<m-1) cos=cost;
                if(dis[v] > dis[u] + min(cos,sum[mau] - cost)){
                     dis[v]=dis[u] + min(cos,sum[mau] - cost);
                    q.push({dis[v],v});
                }
            }
            if(dis[v]>save[mau] + sum[mau] - cost){
                    dis[v]=save[mau] + sum[mau] - cost;
                    q.push({dis[v],v});
            }
        }
    }
//    if(dis[)
}
void solve()
{
    cin>>n>>m;
    fo(i,1,m){
        int u,v,c,p;
        cin>>u>>v>>c>>p;
        adj[u].pb({v,{c,p}});
        adj[v].pb({u,{c,p}});
//        dd[c]=3;
    }
//    ll ans=1e18;
    dijkstra();
//    cout<<dis[3];
    if(dis[n]==1e18) cout<<-1;
    else cout<<dis[n];
}
main()
{
//    freopen("robot1.inp","r",stdin);
//    freopen("robot1.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void dijkstra()':
Main.cpp:37:12: warning: unused variable 'kc' [-Wunused-variable]
   37 |         ll kc=q.top().fi;
      |            ^~
Main.cpp: At global scope:
Main.cpp:105:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  105 | main()
      | ^~~~

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