Submission #935482

#	Time	Username	Problem	Language	Result	Execution time	Memory
935482		weakweakweak	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	169 ms	5712 KiB

ho_t4

//抄解因為我笨，根本就不會最短路徑樹
//煩躁實作
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int,int>
#define fs first
#define sc second
const int inf  = 1e18, binf = inf + 11e9;
pii es[40100];
int n, m, C[40100], D[40100], hase[210][210] = {0}, eid[210][210] = {0}, ontree[40100] = {0};
vector <int> ans1n, ansn1, tree1n, treen1;


pair< vector<int>, vector<int> > Dijkstra(int st, int ed);

int solve (int ei) {
    if (ontree[ei]) {
        int tmp = eid[es[ei].sc][es[ei].fs], tmp2 = hase[es[ei].sc][es[ei].fs];
        hase[es[ei].fs][es[ei].sc] = 0, hase[es[ei].sc][es[ei].fs] = 1;
        eid[es[ei].sc][es[ei].fs] = eid[es[ei].fs][es[ei].sc];
        swap(es[ei].fs, es[ei].sc);
        int res = Dijkstra(1, n).fs[n] + Dijkstra(n, 1).fs[1] + D[ei];
        swap(es[ei].fs, es[ei].sc);
        hase[es[ei].fs][es[ei].sc] = 1, hase[es[ei].sc][es[ei].fs] = tmp2;
        eid[es[ei].sc][es[ei].fs] = tmp;
        return res;
    }
    else { 
        int res = min(ans1n[n] + ansn1[es[ei].fs] + ansn1[es[ei].sc], ans1n[es[ei].sc] + ans1n[es[ei].fs] + ansn1[1]) + C[ei] + D[ei];
        res = min(res, ansn1[es[ei].fs] + ansn1[es[ei].sc] + ans1n[es[ei].sc] + ans1n[es[ei].fs] + C[ei] * 2 + D[ei]); 
        return res;
    }
}


pair< vector<int>, vector<int> > Dijkstra(int st, int ed) {
    vector <int> ans(n + 2, binf), vis(n + 2, 0), tree, from(n + 2, 0);
    ans[st] = 0;
    for (int t = 0; t <= n; t++) {
        int ii = 1;
        for (int i = 1; i <= n; i++) if (!vis[i]) ii = i;
        for (int i = 1; i <= n; i++) if (!vis[i] and ans[i] < ans[ii]) ii = i;
        if (vis[ii] or ans[ii] > inf) break;
        vis[ii] = 1;
        for (int j = 1; j <= n; j++) {
            if (vis[j] or !hase[ii][j]) continue;
            int ei = eid[ii][j];
            if (ans[ii] + C[ei] < ans[j]) {
                ans[j] = ans[ii] + C[ei];
                from[j] = ei;
            }
        }
    }
    for (int i = 1; i <= n; i++) if(i != st) tree.push_back(from[i]);
return {ans, tree};}


signed main () {
    // ios_base :: sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> es[i].fs >> es[i].sc >> C[i] >> D[i];
        hase[es[i].fs][es[i].sc] = 1, eid[es[i].fs][es[i].sc] = i;
    }
    
    auto rEs = Dijkstra (1, n);
    ans1n = rEs.fs, tree1n = rEs.sc;
    rEs = Dijkstra (n, 1);
    ansn1 = rEs.fs, treen1 = rEs.sc;
    for (int x : tree1n) ontree[x] = 1;
    for (int x : treen1) ontree[x] = 1;

    int finans = ans1n[n] + ansn1[1];
    for (int i = 0; i < m; i++) finans = min(finans, solve(i));

    if (finans >= inf) finans = -1;
    cout << finans << '\n';
return 0;}

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