Submission #935702

#	Time	Username	Problem	Language	Result	Execution time	Memory
935702		weakweakweak	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	413 ms	6532 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[50100];
int n, m, C[50100], D[50100], ontree[50100] = {0};
vector <int> ans1n, ansn1, tree1n, treen1, e[210][210];
vector <int> ansxn[210], ansx1[210];
bool notused[50100] = {0};

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

int solve (int ei) {
    if (ontree[ei]) {
        notused[ei] = 1;
        e[es[ei].sc][es[ei].fs] . push_back(m + 1);
        C[m + 1] = C[ei], D[m + 1] = D[ei];
        int res = Dijkstra(1, n).fs[n];
        res += Dijkstra(n, 1).fs[1] + D[ei];
        notused[ei] = 0;
        e[es[ei].sc][es[ei].fs] . pop_back();
        return res;
    }
    else { 
        int res = ans1n[n] + ansn1[es[ei].sc] + ansx1[es[ei].fs][1] + C[ei] + D[ei]; 
        res = min(ans1n[es[ei].sc] + ansxn[es[ei].fs][n] + ansn1[1] + C[ei] + D[ei], res);
        res = min(ans1n[es[ei].sc] + ansxn[es[ei].fs][n] + ansn1[es[ei].sc] + ansx1[es[ei].fs][1] + C[ei] * 2 + D[ei], res);
        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 !e[ii][j].size()) continue;
            for (int ei : e[ii][j] ) {
                if (notused[ei]) continue;
                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];
        e[es[i].fs][es[i].sc].push_back(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;
    for (int i = 1; i <= n; i++) ansxn[i] = Dijkstra (i, n).fs, ansx1[i] = Dijkstra (i, 1).fs;

    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: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 63 / 63