Submission #534769

#	Time	Username	Problem	Language	Result	Execution time	Memory
534769		Rafi22	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	55 ms	5452 KiB

ho_t4

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

const int N=207,M=50007;

struct edge
{
    int u,id;
    ll c,d;
};
vector<edge>G[N][2];
int n,m;
bool is1[M],isn[M];
int o[N],k[N];

vector<ll> dijkstra(int p,int ban,int c)
{
    vector<ll>d(n+1,infl);
    vector<bool>odw(n+1,0);
    memset(o,0,sizeof o);
    memset(k,0,sizeof k);
    d[p]=0;
    while(true)
    {
        int v;
        ll mn=infl;
        for(int i=1;i<=n;i++)
        {
            if(!odw[i]&&d[i]<mn)
            {
                v=i;
                mn=d[i];
            }
        }
        if(mn==infl) break;
        odw[v]=1;
        for(auto e:G[v][c])
        {
            if(e.id==ban) continue;
            if(d[v]+e.c<d[e.u])
            {
                d[e.u]=d[v]+e.c;
                o[e.u]=v;
                k[e.u]=e.id;
            }
        }
    }
    return d;
}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        ll c,d;
        cin>>u>>v>>c>>d;
        G[u][0].pb({v,i,c,d});
        G[v][1].pb({u,i,c,d});
    }
    vector<ll>D1=dijkstra(1,-1,0);
    int x=n;
    if(D1[n]==infl) x=0;
    while(x)
    {
        is1[k[x]]=1;
        x=o[x];
    }
    vector<ll>D1r=dijkstra(1,-1,1);
    vector<ll>Dn=dijkstra(n,-1,0);
    x=1;
    if(Dn[1]==infl) x=0;
    while(x)
    {
        isn[k[x]]=1;
        x=o[x];
    }
    vector<ll>Dnr=dijkstra(n,-1,1);
    ll ans=min(infl,D1[n]+Dn[1]);
    for(int v=1;v<=n;v++)
    {
        for(auto e:G[v][0])
        {
            ll ne=D1[e.u]+Dnr[v]+e.d+e.c;
            if(isn[e.id])
            {
                G[e.u][0].pb({v,-1,e.c,e.d});
                vector<ll>neD=dijkstra(n,e.id,0);
                G[e.u][0].pop_back();
                ne+=neD[1];
            }
            else ne+=Dn[1];
            ans=min(ans,ne);
            ne=Dn[e.u]+D1r[v]+e.d+e.c;
            if(is1[e.id])
            {
                G[e.u][0].pb({v,-1,e.c,e.d});
                vector<ll>neD=dijkstra(1,e.id,0);
                G[e.u][0].pop_back();
                ne+=neD[n];
            }
            else ne+=D1[n];
            ans=min(ans,ne);
        }
    }
    if(ans==infl) cout<<-1;
    else cout<<ans;

    return 0;
}

Compilation message (stderr)

ho_t4.cpp: In function 'std::vector<long long int> dijkstra(int, int, int)':
ho_t4.cpp:55:23: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |                 o[e.u]=v;
      |                 ~~~~~~^~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63