Submission #247538

#	Time	Username	Problem	Language	Result	Execution time	Memory
247538		Atill83	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	64 ms	8556 KiB

ho_t4

#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 50000;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n, m;


struct ed{
    ll v, i, dist;

    bool operator < (ed other) const {
        return dist > other.dist;
    };
};

pair<ll, ed> edg[MAXN];
vector<ed> adj[MAXN];
int d[MAXN];
ll fw[205][205], fw1[205][205], fw2[205][205];
int p1[MAXN], p2[MAXN];
ll ans[MAXN];


vector<int> dik(int u, int v){
    vector<ll> dst(n + 1, -1);
    vector<ll> to(n + 1, -1);
    priority_queue<ed> pq;
    pq.push({u, -1, 0});
    while(!pq.empty()){
        ed cur = pq.top();
        pq.pop();
        if(dst[cur.v] != -1){
            continue;
        }
        dst[cur.v] = cur.dist;
        to[cur.v] = cur.i;
        for(ed a: adj[cur.v]){
            if(dst[a.v] == -1){
                pq.push({a.v, a.i, dst[cur.v] + a.dist});
            }
        }
    }
    if(dst[v] == -1){
        return {};
    }
    vector<int> res;
    int cur = v;
    while(cur != u){
        res.push_back(to[cur]);
        cur = edg[to[cur]].ff;
    }
    reverse(res.begin(), res.end());
    return res;
}



int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>n>>m;
    for(int i = 0; i < m; i++){
        int u, v, c, dd;
        cin>>u>>v>>c>>dd;
        d[i] = dd;
        ed a = {v, i, c};
        adj[u].push_back(a);
        edg[i] = {u, a};
    }

    vector<int> path1 = dik(1, n), path2 = dik(n, 1);

    for(int i = 0; i < path1.size(); i++)
        p1[path1[i]] = i + 1;
    for(int i = 0; i < path2.size(); i++) 
        p2[path2[i]] = i + 1;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++){
            if(i == j){
                fw[i][j] = fw1[i][j] = fw2[i][j] = 0;
            }else{
                fw[i][j] = fw1[i][j] = fw2[i][j] = INF;
            }
        }
    
    for(int i = 0; i < m; i++){
        fw[edg[i].ff][edg[i].ss.v] = min(fw[edg[i].ff][edg[i].ss.v],edg[i].ss.dist);
        if(!p1[i]) fw1[edg[i].ff][edg[i].ss.v] = min(fw1[edg[i].ff][edg[i].ss.v], edg[i].ss.dist);
        if(!p2[i]) fw2[edg[i].ff][edg[i].ss.v] = min(fw2[edg[i].ff][edg[i].ss.v], edg[i].ss.dist);
    }



    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++){
                fw[i][j] = min(fw[i][j], fw[i][k] + fw[k][j]);
                fw1[i][j] = min(fw1[i][j], fw1[i][k] + fw1[k][j]);
                fw2[i][j] = min(fw2[i][j], fw2[i][k] + fw2[k][j]);
            }

    ll cev = fw[1][n] + fw[n][1];

    for(int i = 0; i < m; i++){
        if(!p1[i]){
            ll sim = INF;
            sim = min(fw[1][n], fw[1][edg[i].ss.v] + fw[edg[i].ff][n] + edg[i].ss.dist);
            ans[i] += sim;
        }else{
            ll sim = INF;
            for(int l = 0; l < p1[i]; l++){
                for(int k = p1[i]; k <= path1.size(); k++){
                    int u = edg[path1[l]].ff, v = edg[path1[k - 1]].ss.v;
                    sim = min(sim, fw[1][u] + fw1[u][v] + fw[v][n]);
                }
            }
            ans[i] += sim;
        }
    }
    //for(int j: path2) cout<<j<<" "; cout<<endl;

    for(int i = 0; i < m; i++){
        if(!p2[i]){
            ll sim = INF;
            sim = min(fw[n][1], fw[n][edg[i].ss.v] + fw[edg[i].ff][1] + edg[i].ss.dist);
            //if(i == 3) cout<<sim<<endl;
            ans[i] += sim;
        }else{
            ll sim = INF;
            for(int l = 0; l < p2[i]; l++){
                for(int k = p2[i]; k <= path2.size(); k++){
                    int u = edg[path2[l]].ff, v = edg[path2[k - 1]].ss.v;
                    sim = min(sim, fw[n][u] + fw2[u][v] + fw[v][1]);
                }
            }
            ans[i] += sim;
        }
    }

    for(int i = 0; i < m; i++){
        //cout<<ans[i]<<endl;
        cev = min(cev, ans[i] + d[i]);
    }


    if(cev >= INF) cev = -1;


    cout<<cev<<endl;


    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Compilation message (stderr)

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:88:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < path1.size(); i++)
                    ~~^~~~~~~~~~~~~~
ho_t4.cpp:90:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < path2.size(); i++) 
                    ~~^~~~~~~~~~~~~~
ho_t4.cpp:128:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int k = p1[i]; k <= path1.size(); k++){
                                    ~~^~~~~~~~~~~~~~~
ho_t4.cpp:147:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int k = p2[i]; k <= path2.size(); k++){
                                    ~~^~~~~~~~~~~~~~~

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