Submission #699463

#	Time	Username	Problem	Language	Result	Execution time	Memory
699463		Cross_Ratio	Olympic Bus (JOI20_ho_t4)	C++14	11 / 100	1086 ms	7860 KiB

ho_t4

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e18;
int dis[205][205];
array<int, 4> Edge[50005];
vector<array<int, 3>> adj1[205], adj2[205];
int dist[205];
bool vis[205];
int adj[205][205];
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N, M;
    cin >> N >> M;
    int i, j;
    clock_t st = clock();
    for(i=0;i<N;i++) {
        for(j=0;j<N;j++) dis[i][j] = INF;
        dis[i][i] = 0;
    }
    for(i=0;i<M;i++) {
        int a, b, c, d;
        //a = rand()%N+1, b = rand()%N+1, c = rand(), d = rand();
        cin >> a >> b >> c >> d;
        Edge[i] = {a-1, b-1, c, d};
        dis[a-1][b-1] = min(dis[a-1][b-1], c);
    }
    for(int k = 0; k < N; k++) {
        for(i=0;i<N;i++) {
            for(j=0;j<N;j++) {
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
    for(i=0;i<M;i++) {
        adj1[Edge[i][0]].push_back({Edge[i][1], i});
        adj2[Edge[i][1]].push_back({Edge[i][0], i});
    }
    set<int> S;
    for(i=0;i<N;i++) dist[i] = INF;
    dist[0] = 0;
    priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int,2>>> PQ;
    PQ.push({0, 0});
    while(!PQ.empty()) {
        auto k = PQ.top();
        PQ.pop();
        int id = k[1];
        if(dist[id] != k[0]) continue;
        for(auto n : adj1[id]) {
            if(dist[n[0]] > dist[id] + Edge[n[1]][2]) {
                dist[n[0]] = dist[id] + Edge[n[1]][2];
                PQ.push({dist[n[0]], n[0]});
            }
        }
    }
    int pt = N-1;
    if(dist[N-1]!=INF) {
        while(pt != 0) {
            int prv = pt;
            for(auto n : adj2[pt]) {
                if(pt == n[0]) continue;
                if(dist[n[0]] + Edge[n[1]][2] == dist[pt]) {
                    S.insert(n[1]);
                    pt = n[0];
                    break;
                }
            }
            assert(pt != prv);
        }
    }
    for(i=0;i<N;i++) dist[i] = INF;
    dist[N-1] = 0;
    PQ = priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int,2>>> {};
    PQ.push({0, N-1});
    while(!PQ.empty()) {
        auto k = PQ.top();
        PQ.pop();
        int id = k[1];
        if(dist[id] != k[0]) continue;
        for(auto n : adj1[id]) {
            if(dist[n[0]] > dist[id] + Edge[n[1]][2]) {
                dist[n[0]] = dist[id] + Edge[n[1]][2];
                PQ.push({dist[n[0]], n[0]});
            }
        }
    }
    pt = 0;
    if(dist[0]!=INF) {
        while(pt != N-1) {
            int prv = pt;
            for(auto n : adj2[pt]) {
                if(pt == n[0]) continue;
                if(dist[n[0]] + Edge[n[1]][2] == dist[pt]) {
                    S.insert(n[1]);
                    pt = n[0];
                    break;
                }
            }
            assert(pt != prv);
        }
    }
    int mi = dis[0][N-1] + dis[N-1][0];
    for(i=0;i<M;i++) {
        if(S.find(i) != S.end()) continue;
        int val = Edge[i][3];
        int d1 = dis[0][N-1], d2 = dis[N-1][0];
        int a = Edge[i][0], b = Edge[i][1], c = Edge[i][2];
        d1 = min(d1, dis[0][b] + c + dis[a][N-1]);
        d2 = min(d2, dis[N-1][b] + c + dis[a][0]);
        mi = min(mi, val + d1 + d2);
        //cout << i << " : " << val << ' ' << d1 << ' ' << d2 << '\n';
    }
    assert(S.size() < 2*N);
    for(int n : S) {
        int val = Edge[n][3];
        for(i=0;i<N;i++) {
            for(j=0;j<N;j++) adj[i][j] = INF;
            adj[i][i] = 0;
        }
        for(i=0;i<M;i++) {
            if(i==n) {
                adj[Edge[i][1]][Edge[i][0]] = min(adj[Edge[i][1]][Edge[i][0]], Edge[i][2]);
            }
            else adj[Edge[i][0]][Edge[i][1]] = min(adj[Edge[i][0]][Edge[i][1]], Edge[i][2]);
        }
        for(i=0;i<N;i++) vis[i] = false;
        for(i=0;i<N;i++) dist[i] = INF;
        dist[0] = 0;
        while(true) {
            int mi = INF, pt = -1;
            for(i=0;i<N;i++) {
                if(!vis[i] && mi > dist[i]) {
                    mi = dist[i];
                    pt = i;
                }
            }
            if(pt == -1) break;
            vis[pt] = true;
            for(i=0;i<N;i++) {
                if(dist[i] > dist[pt] + adj[pt][i]) {
                    dist[i] = dist[pt] + adj[pt][i];
                }
            }
        }
        if(dist[N-1]==INF) continue;
        val += dist[N-1];
        for(i=0;i<N;i++) vis[i] = false;
        for(i=0;i<N;i++) dist[i] = INF;
        dist[N-1] = 0;
        while(true) {
            int mi = INF, pt = -1;
            for(i=0;i<N;i++) {
                if(!vis[i] && mi > dist[i]) {
                    mi = dist[i];
                    pt = i;
                }
            }
            if(pt == -1) break;
            vis[pt] = true;
            for(i=0;i<N;i++) {
                if(dist[i] > dist[pt] + adj[pt][i]) {
                    dist[i] = dist[pt] + adj[pt][i];
                }
            }
        }
        if(dist[0]==INF) continue;
        val += dist[0];
        mi = min(mi, val);
    }
    cout << (mi <= 1e17 ? mi : -1);
    //cout << '\n' << clock() - st <<"ms";
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from ho_t4.cpp:1:
ho_t4.cpp: In function 'int main()':
ho_t4.cpp:115:21: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  115 |     assert(S.size() < 2*N);
      |            ~~~~~~~~~^~~~~
ho_t4.cpp:18:13: warning: unused variable 'st' [-Wunused-variable]
   18 |     clock_t st = clock();
      |             ^~

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