Submission #699468

#	Time	Username	Problem	Language	Result	Execution time	Memory
699468		Cross_Ratio	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	189 ms	5580 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];
int dist[205];
bool vis[205];
int adj[205][205];
int opt[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});
    }
    set<int> S;
    for(i=0;i<N;i++) dist[i] = INF;
    for(i=0;i<N;i++) vis[i] = false;
    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(vis[id]) continue;
        vis[id] = true;
        for(auto n : adj1[id]) {
            if(dist[n[0]] > dist[id] + Edge[n[1]][2]) {
                dist[n[0]] = dist[id] + Edge[n[1]][2];
                opt[n[0]] = n[1];
                PQ.push({dist[n[0]], n[0]});
            }
        }
    }
    for(i=0;i<N;i++) vis[i] = false;
    int pt = N-1;
    if(dist[N-1]!=INF) {
        while(pt != 0) {
            S.insert(opt[pt]);
            pt = Edge[opt[pt]][0];
        }
    }
    for(i=0;i<N;i++) dist[i] = INF;
    for(i=0;i<N;i++) vis[i] = false;
    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(vis[id]) continue;
        vis[id] = true;
        for(auto n : adj1[id]) {
            if(dist[n[0]] > dist[id] + Edge[n[1]][2]) {
                dist[n[0]] = dist[id] + Edge[n[1]][2];
                opt[n[0]] = n[1];
                PQ.push({dist[n[0]], n[0]});
            }
        }
    }
    for(i=0;i<N;i++) vis[i] = false;
    pt = 0;
    if(dist[0]!=INF) {
        while(pt != N-1) {
            S.insert(opt[pt]);
            pt = Edge[opt[pt]][0];
        }
    }
    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:107: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]
  107 |     assert(S.size() < 2*N);
      |            ~~~~~~~~~^~~~~
ho_t4.cpp:19:13: warning: unused variable 'st' [-Wunused-variable]
   19 |     clock_t st = clock();
      |             ^~

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