Submission #250460

#	Time	Username	Problem	Language	Result	Execution time	Memory
250460		combi1k1	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	707 ms	3256 KiB

ho_t4

#include<bits/stdc++.h>

using namespace std;

#define ll  long long
#define ld  double

#define sz(x)   (int)x.size()
#define all(x)  x.begin(),x.end()

#define pb  emplace_back
#define X   first
#define Y   second

const int   N   = 205;
const ll    inf = 1e18;

typedef pair<ll,int>    ii;

struct Edge {
    int u, v;
    int cost;

    Edge(int _u = 0,int _v = 0,int _c = 0) : u(_u), v(_v), cost(_c) {}
};
vector<Edge> E;
vector<int>  g[N];

bool use[50009];
ll  ans[50009];
ll  dis[209][209];

int main()  {
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
 
    int n;  cin >> n;
    int m;  cin >> m;

    for(int i = 1 ; i <= n ; ++i)
    for(int j = 1 ; j <= n ; ++j)
        dis[i][j] = (i == j ? 0 : inf);
    
    for(int i = 0 ; i < m ; ++i)    {
        int x, y;   cin >> x >> y;
        int c, d;   cin >> c >> ans[i];

        g[x].pb(i);
        E.pb(x,y,c);

        if (dis[x][y] > c)
            dis[x][y] = c;
    }
    for(int k = 1 ; k <= n ; ++k)
        for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= n ; ++j)
            dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]);
        
    auto FindPath = [&](int S,int T)    {
        vector<ll>  d(n + 1,inf);
        vector<int> p(n + 1,-1);

        priority_queue<ii,vector<ii>,greater<ii> >  pq;
        pq.push(ii(0,S));

        d[S] = 0;

        while (pq.size())   {
            int u  = pq.top().Y;
            ll  du = pq.top().X;    pq.pop();

            if (du != d[u])
                continue;
            
            for(int i : g[u])   {
                int v = E[i].v;

                if (d[v] > du + E[i].cost)  {
                    d[v] = du + E[i].cost;
                    p[v] = i;

                    pq.push(ii(d[v],v));
                }
            }
        }
        if (p[T] < 0)   return;

        while (T != S)  {
            int i = p[T];
            use[i] = 1;
            T = E[i].u;
        }
    };
    auto dijkstra = [&](int S,int T,int ban)    {
        vector<ll>  d(n + 1,inf);

        priority_queue<ii,vector<ii>,greater<ii> >  pq;
        pq.push(ii(0,S));

        d[S] = 0;

        while (pq.size())   {
            int u  = pq.top().Y;
            ll  du = pq.top().X;    pq.pop();

            if (du != d[u])
                continue;
            
            for(int i : g[u])   if (i != ban)   {
                int v = E[i].v;

                if (d[v] > du + E[i].cost)  {
                    d[v] = du + E[i].cost;
                    pq.push(ii(d[v],v));
                }
            }
        }
        return  d[T];
    };
    ll  Result = dis[1][n] + dis[n][1];

    FindPath(1,n);

    for(int i = 0 ; i < m ; ++i)    {
        if (use[i]) ans[i] += dijkstra(1,n,i);
        else        ans[i] += min(dis[1][n],dis[1][E[i].v] + E[i].cost + dis[E[i].u][n]);

        use[i] = 0;
    }
    FindPath(n,1);

    for(int i = 0 ; i < m ; ++i)    {
        if (use[i]) ans[i] += dijkstra(n,1,i);
        else        ans[i] += min(dis[n][1],dis[n][E[i].v] + E[i].cost + dis[E[i].u][1]);
    }
    for(int i = 0 ; i < m ; ++i)
        if (Result > ans[i])
            Result = ans[i];
    
    if (Result >= 1e18)
        Result = -1;
    
    cout << Result << endl;
}

Compilation message (stderr)

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:46:16: warning: unused variable 'd' [-Wunused-variable]
         int c, d;   cin >> c >> ans[i];
                ^

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