首页 > 其他分享 >P4021 [CTSC2012] 最短路

P4021 [CTSC2012] 最短路

时间:2024-01-05 21:25:41浏览次数:41  
标签:pre dist P4021 测试点 int 短路 vector CTSC2012 id

[CTSC2012] 最短路

Luogu P4021

题目描述

给定一个节点 \(1\) 和节点 \(n\) 连通的正权无向图 \(G\),请你删除不超过 \(k\) 条边,使得节点 \(1\) 和节点 \(n\) 仍然连通的同时,且这两点之间的最短路尽可能长。

提交答案题。

Solution

模拟赛考到这道,改完这道题我爆了。

提交答案题一般是模拟退火逼近最优解,或者是观察数据特征求解。然后我在赛时敲了一个模拟退火,获得了 \(42\) 分的高分(逃)。

谴责出题人不把评分标准告诉我。

尝试观察数据特征,接下来将会分别讨论每一个测试点的数据特征以及对应的解题策略。

测试点 1

数据范围很小,随便搜一下就可以很快的跑出答案。具体就是直接枚举每条边是否在答案出现,然后暴力跑一下最短路,取最优答案输出即可。随便跑跑就有解了。

代码没写。

测试点 2 / 3

虽然 \(n,m\) 增大了,但是 \(K\) 仍然不大,所以考虑继续搜。直接使用测试点 1 的做法跑的话根本跑不出来,考虑剪一下枝。

注意到每次删除掉的边显然只能够是当前最短路上的边,否则一定不优。所以每次删边时先用 Dijstra 找出最短路径,然后枚举路径上的边进行删除。

对于测试点 1 使用这个做法大约能在 \(0.1\) 秒上下跑出答案,测试点 2 大约 \(10\) 秒,测试点 3 大约 \(12\) 分钟左右。

其实可以写成找到一个新答案就输出的形式,这样测试点 3 其实跑不到 \(20\) 秒就能跑出最优解,求稳的话还是等跑完吧。

具体实现:

solve1
#include <bits/stdc++.h>
using namespace std;
const string file = "shortest3";
const int _N = 2e4 + 5, inf = 0x3f3f3f3f;
int N, M, K;
struct Edge {int nxt, to, w, id;} edge[_N];
int tot = 1, head[_N];
void addEdge(int x, int y, int w, int id) {
    edge[++tot] = {head[x], y, w, id}; head[x] = tot;
}
pair<vector<int>, int> getPath(vector<bool> &flag) {
    priority_queue<pair<int, int>> q;
    vector<bool> vis(N + 1, 0);
    vector<int> dist(N + 1, inf);
    vector<int> pre(N + 1, 0);
    dist[1] = 0; q.emplace(0, 1);
    while (!q.empty()) {
        int x = q.top().second; q.pop();
        if (vis[x]) continue;
        vis[x] = 1;
        for (int i = head[x]; i; i = edge[i].nxt) {
            int v = edge[i].to, w = edge[i].w, id = i;
            if (!flag[edge[i].id]) continue;
            if (dist[v] > dist[x] + w) {
                dist[v] = dist[x] + w;
                pre[v] = id;
                q.emplace(-dist[v], v);
            }
        }
    }
    vector<int> res;
    for (int x = N; x; x = edge[pre[x]^1].to)
        if (pre[x]) res.emplace_back(edge[pre[x]].id);
    return {res, dist[N]};
}
int ans = 0;
vector<bool> finFlag;
void dfs(int k, vector<bool> &flag) {
    auto res = getPath(flag);
    if (res.second == inf) return ;
    if (k == K + 1) {
        if (res.second > ans) {
            finFlag = flag, ans = res.second;
            vector<int> res;
            for (int i = 1; i <= M; ++i) if (!finFlag[i])
                res.emplace_back(i);
            ofstream fout(file + ".out");
            fout << res.size() << '\n';
            for (int x: res) fout << x << '\n';
            fout.close();
        }
        return ;
    }
    for (int x: res.first) {
        flag[x] = 0;
        dfs(k + 1, flag);
        flag[x] = 1;
    }
}
signed main() {
    ifstream fin(file + ".in");
    fin >> N >> M >> K;
    for (int i = 1; i <= M; ++i) {
        int x, y, w; fin >> x >> y >> w;
        addEdge(x, y, w, i), addEdge(y, x, w, i);
    }
    fin.close();
    vector<bool> tmp(M + 1, 1);
    dfs(1, tmp);
}

测试点 4

发现 \(m=k\),也就是删边无限制,换言之就是要求出一条从 \(1\) 到 \(n\) 的最长路径。因为 \(n=20\),所以可以直接状压 DP 解决。设 \(f(i,S)\) 表示当前在 \(i\),经过的点集为 \(S\),转移 \(f(i,S)+d(i,j)\to f(j,S\cup \{j\})\)。可以在 \(1\) 秒内得到解。

solve4
#include <bits/stdc++.h>
using namespace std;
const int _N = 20 + 1;
int f[_N][_N], id[_N][_N], N, M, K;
int F[_N][1 << _N];
pair<int, int> pre[_N][1 << _N];
signed main() {
    freopen("shortest4.in", "r", stdin);
    freopen("shortest4.out", "w", stdout);
    cin.tie(0); cout.tie(0);
    cin >> N >> M >> K;
    memset(f, 0xcf, sizeof f);
    for (int i = 1; i <= M; ++i) {
        int x, y, w; cin >> x >> y >> w;
        if (w > f[x][y]) {
            f[x][y] = f[y][x] = w;
            id[x][y] = id[y][x] = i;
        }
    }
    vector<int> S;
    for (int i = 1; i < (1 << N); ++i) S.emplace_back(i);
    sort(S.begin(), S.end(), [](const int &i, const int &j) {
        return __builtin_popcount(i) < __builtin_popcount(j);
    });
    memset(F, 0xcf, sizeof F);
    F[1][1] = 0;
    for (int s: S) {
        for (int i = 1; i <= N; ++i) if ((s >> (i - 1)) & 1) {
            for (int j = 1; j <= N; ++j) {
                if ((s >> (j - 1)) & 1) continue;
                int ts = s | (1 << (j - 1));
                if (F[i][s] + f[i][j] > F[j][ts]) {
                    F[j][ts] = F[i][s] + f[i][j];
                    pre[j][ts] = {i, s};
                }
            }
        }
    }
    int pos = max_element(F[N] + 1, F[N] + (1 << N)) - F[N];
    vector<bool> res(M + 1, 0);
    for (pair<int, int> x(N, pos); x.first; x = pre[x.first][x.second]) {
        int lst = pre[x.first][x.second].first;
        if (lst) res[id[lst][x.first]] = 1;
    }
    vector<int> ans;
    for (int i = 1; i <= M; ++i) if (!res[i])
        ans.emplace_back(i);
    cout << ans.size() << '\n';
    for (int x: ans) cout << x << '\n';
}

测试点 5

这个点其实与测试点 4 类似,虽然表面上很难看出来。这个点中 \(1000\) 个点被划分成为了 \(50\) 个块,每个块内有 \(20\) 个点,相邻块间有 \(1\) 条边。

具体做法与测试点 4 类似,先对每一个块跑出最优解,然后把所有块的解拼在一起即可。

一个块跑 \(1\) 秒左右,\(50\) 个块可以在 \(1\) 分钟内跑出来。

solve5
#include <bits/stdc++.h>
using namespace std;
const int _N = 2e4 + 5;
int N, M, K, len = 20, bl[_N];
struct Edge {int x, y, w, id;} edge[_N];
vector<Edge> vec[_N];
int f[21][1 << 21], d[21][21], num[21][21];
pair<int, int> pre[21][1 << 21];
vector<int> S;
bool flag[_N];
void solve(int id) {
    memset(f, 0xcf, sizeof f), memset(d, 0xcf, sizeof d), memset(num, 0, sizeof num);
    for (int i = 0; i <= len; ++i) for (int s = 0; s < (1 << len); ++s)
        pre[i][s] = {0, 0};
    for (auto e: vec[id]) {
        int x = e.x, y = e.y, w = e.w, i = e.id;
        x -= (id - 1) * len, y -= (id - 1) * len;
        if (w > d[x][y]) {
            d[y][x] = d[x][y] = w;
            num[y][x] = num[x][y] = i;
        }
    }
    f[1][1] = 0;
    for (int s: S)
        for (int i = 1; i <= len; ++i) if (s >> (i - 1) & 1)
            for (int j = 1; j <= len; ++j) {
                if (s >> (j - 1) & 1) continue;
                int ts = s | (1 << (j - 1));
                if (f[i][s] + d[i][j] > f[j][ts]) {
                    f[j][ts] = f[i][s] + d[i][j];
                    pre[j][ts] = {i, s};
                }
            }
    int pos = max_element(f[len] + 1, f[len] + (1 << len)) - f[len];
    cerr << id << ": " << f[len][pos] << '\n';
    for (pair<int, int> x(len, pos); x.first; x = pre[x.first][x.second]) {
        int lst = pre[x.first][x.second].first;
        if (lst) flag[num[lst][x.first]] = 1;
    }
}
signed main() {
    freopen("shortest5.in", "r", stdin);
    freopen("shortest5.out", "w", stdout);
    cin.tie(0); cout.tie(0);
    cin >> N >> M >> K;
    for (int i = 1; i <= N; ++i) bl[i] = (i - 1) / len + 1;
    for (int i = 1; i <= M; ++i) {
        int x, y, w; cin >> x >> y >> w;
        if (bl[x] == bl[y])
            vec[bl[x]].push_back({x, y, w, i});
        else flag[i] = 1;
    }
    for (int i = 1; i < (1 << len); ++i)
        S.emplace_back(i);
    sort(S.begin(), S.end(), [](const int& i, const int& j) {
        return __builtin_popcount(i) < __builtin_popcount(j);
    });
    for (int i = 1; i <= N / len; ++i) solve(i);
    vector<int> ans;
    for (int i = 1; i <= M; ++i) if (!flag[i])
        ans.emplace_back(i);
    cout << ans.size() << '\n';
    for (int x: ans) cout << x << '\n';
}

测试点 6 / 7

这两个点特征与测试点 5 类似,为 \(1000\) 个点被分为了 \(100\) 个块,每个块内有 \(10\) 个点,相邻块间有 \(1\) 条边,块内分别有 \(10\) 条边(测试点 6)和 \(20\) 条边(测试点 7)。但是这两个点不保证 \(m=k\),因此不能直接状压 DP。

因为每个块内的边数和点数很少,所以可以使用测试点 1 的做法跑出每个块 \(i\) 删除 \(j\) 条边时的答案 \(f(i,j)\),然后对于所有块做背包即可。

每个块 \(0.6\) 秒上下,所有块能在 \(1\) 分钟左右跑完。

solve6
#include <bits/stdc++.h>
using namespace std;
const int _N = 2e4 + 5, inf = 0x3f3f3f3f;
int N, M, K, bl[_N];
struct Edge {int x, y, w, id;};
vector<Edge> vec[101];
bool flag[_N];
int dist[21];
vector<pair<int, int>> e[21];
bool vis[_N];
void dij() {
    memset(vis, 0, sizeof vis);
    memset(dist, 0x3f, sizeof dist);
    priority_queue<pair<int, int>> q;
    q.emplace(0, 1); dist[1] = 0;
    while (!q.empty()) {
        int x = q.top().second; q.pop();
        if (vis[x]) continue;
        vis[x] = 1;
        for (auto [v, w]: e[x]) if (dist[v] > dist[x] + w) {
            dist[v] = dist[x] + w;
            q.emplace(-dist[v], v);
        }
    }
}
int met[101][21];
int val[101][21];
int tot = 20;
void getVal(int id) {
    memset(val[id], 0xcf, sizeof val[id]);
    for (int S = 0; S < (1 << tot); ++S) {
        for (int i = 1; i <= 10; ++i) e[i].clear();
        for (int i = 0; i < tot; ++i) if (S & (1 << i)) {
            int x = vec[id][i].x - 10 * (id - 1), y = vec[id][i].y - 10 * (id - 1), w = vec[id][i].w;
            e[x].emplace_back(y, w), e[y].emplace_back(x, w);
        }
        dij();
        int cnt = tot - __builtin_popcount(S);
        if (dist[10] != inf && dist[10] > val[id][cnt])
            val[id][cnt] = dist[10], met[id][cnt] = S;
    }
}
int f[101][_N], pre[101][_N];
signed main() {
    freopen("shortest7.in", "r", stdin);
    freopen("shortest7.out", "w", stdout);
    cin.tie(0); cout.tie(0);
    cin >> N >> M >> K;
    for (int i = 1; i <= N; ++i) bl[i] = (i - 1) / 10 + 1;
    for (int i = 1; i <= M; ++i) {
        int x, y, w; cin >> x >> y >> w;
        if (bl[x] == bl[y])
            vec[bl[x]].push_back({x, y, w, i});
        else flag[i] = 1;
    }
    for (int i = 1; i <= 100; ++i) getVal(i);
    memset(f, 0xcf, sizeof f);
    f[0][0] = 0;
    for (int i = 1; i <= 100; ++i) {
        for (int j = 0; j <= K; ++j) {
            for (int t = 0; t <= min(j, tot); ++t) {
                int res = f[i-1][j-t] + val[i][t];
                if (res > f[i][j])
                    f[i][j] = res, pre[i][j] = t;
            }
        }
    }
    int pos = max_element(f[100], f[100] + K + 1) - f[100];
    for (int i = 100; i; --i) {
        int S = met[i][pre[i][pos]];
        for (int j = 0; j < tot; ++j) if (S & (1 << j))
            flag[vec[i][j].id] = 1;
        pos = pos - pre[i][pos];
    }
    vector<int> ans;
    for (int i = 1; i <= M; ++i) if (!flag[i])
        ans.emplace_back(i);
    cout << ans.size() << '\n';
    for (int x: ans) cout << x << '\n';
}

测试点 8

这个测试点其实是一个 \(100\) 行 \(100\) 列的网格图。手模较小的数据,比如 \(n\) 行 \(n\) 列(\(n\) 为偶数),容易发现答案为 \(n^2-2\),并得出构造方法,且无法构造出 \(n^2-1\) 的解。

这个比较好写。

solve8
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
inline pii id(int x) {return {(x - 1) / 100 + 1, (x - 1) % 100 + 1};}
int N, M, K;
map<pair<pii, pii>, int> mp;
signed main() {
    freopen("shortest8.in", "r", stdin);
    freopen("shortest8.out", "w", stdout);
    cin.tie(0)->sync_with_stdio(0);
    cin >> N >> M >> K;
    vector<bool> rem(M + 1, 0);
    for (int i = 1; i <= M; ++i) {
        int x, y, w; cin >> x >> y >> w;
        mp[{id(x), id(y)}] = mp[{id(y), id(x)}] = i;
    }
    for (int i = 1; i <= 98; ++i) {
        for (int j = 1; j <= 99; ++j)
            rem[mp[{{i, j}, {i, j + 1}}]] = 1;
        if (i & 1) rem[mp[{{i, 100}, {i + 1, 100}}]] = 1;
        else rem[mp[{{i, 1}, {i + 1, 1}}]] = 1;
    }
    for (int i = 1; i <= 99; ++i) {
        rem[mp[{{99, i}, {100, i}}]] = 1;
        if (i & 1) rem[mp[{{100, i}, {100, i + 1}}]] = 1;
        else rem[mp[{{99, i}, {99, i + 1}}]] = 1;
    }
    vector<int> ans;
    for (int i = 1; i <= M; ++i) if (!rem[i])
        ans.emplace_back(i);
    cout << ans.size() << '\n';
    for (int x: ans) cout << x << '\n';
}

测试点 9

这个点是一个 \(2\) 行 \(1000\) 列,被删去了很少边的网格图。将删去的边的边权设为 \(-\infty\),设 \(a(i,j)\) 表示 \((i,j)\to(i,j+1)\) 的边权,\(b(i)\) 表示 \((0,i)\to(1,i)\) 的边权,那么不难有一个 DP:

设 \(f(i,j)\) 表示 \((1,1)\to(i,j)\) 的最优解,那么有转移:

\[\begin{array}{rll} f(0,i)&\gets&\max\{f(0,i-1)+a(0,i-1),f(1,i-1)+a(1,i-1)+b(i)\}\\ f(1,i)&\gets&\max\{f(0,i-1)+a(0,i-1)+b(i),f(1,i-1)+a(1,i-1)\} \end{array} \]

记录一下决策点以便输出方案。

solve9
#include <bits/stdc++.h>
using namespace std;
int N, M, K;
int a[2][1005], b[1005], f[2][1005];
int ida[2][1005], idb[1005];
int pre[2][1005];
signed main() {
    freopen("shortest9.in", "r", stdin);
    freopen("shortest9.out", "w", stdout);
    cin >> N >> M >> K;
    memset(a, 0xcf, sizeof a), memset(b, 0xcf, sizeof b);
    for (int i = 1; i <= M; ++i) {
        int x, y, w; cin >> x >> y >> w;
        if (y - x == 1) a[x > 1000][x % 1000] = w, ida[x > 1000][x % 1000] = i;
        else b[x] = w, idb[x] = i;
    }
    f[1][0] = 0, f[1][1] = b[1];
    for (int i = 2; i <= 1000; ++i) {
        {
            int res1 = f[0][i-1] + a[0][i-1];
            int res2 = f[1][i-1] + a[1][i-1] + b[i];
            if (res1 < res2) f[0][i] = res2, pre[0][i] = 1;
            else f[0][i] = res1, pre[0][i] = 0;
        } {
            int res1 = f[0][i-1] + a[0][i-1] + b[i];
            int res2 = f[1][i-1] + a[1][i-1];
            if (res1 < res2) f[1][i] = res2, pre[1][i] = 1;
            else f[1][i] = res1, pre[1][i] = 0;
        }
    }
    cerr << f[1][1000] << '\n';
    vector<bool> rem(M + 1, 0);
    int pos = 1;
    for (int i = 1000; i; --i) {
        if (pos ^ pre[pos][i]) {
            rem[idb[i]] = 1;
            rem[ida[pos^1][i-1]] = 1;
        } else rem[ida[pos][i-1]] = 1;
        pos = pre[pos][i];
    }
    vector<int> ans;
    for (int i = 1; i <= M; ++i) if (!rem[i])
        ans.emplace_back(i);
    cout << ans.size() << '\n';
    for (int x: ans) cout << x << '\n';
}

测试点 10

看起来数据毫无规律,但是 \(m-k=n-1\),所以不妨猜这张图存在一条哈密顿路,事实证明也确实如此。

但是直接搜哈密顿路也是根本搜不出来的(至少我没搜出来),发现 \(k=100\),也就是说其实有很多点的度数都是 \(2\) 及以下的,这些点连接的边肯定是不能够被删掉的,所以只需要关心那些度数大于 \(2\) 的点。

写个程序跑一下发现度数大于 \(2\) 的点数量为 \(200\),也就是说所有的非法点度数都为 \(3\)。由于度数为 \(2\) 的点连接的边不能够被删掉,因此可以被删掉的边一定两侧点的度数都为 \(3\)。再跑一下发现这样的边数量仅有 \(101\) 条,也就是说只需要从这 \(101\) 条边中选一条删掉就行了。所以直接枚举删掉哪一条边,然后暴力 check 一下就行了。

solve10
#include <bits/stdc++.h>
using namespace std;
const int _N = 2e4 + 5;
int N, M, K, deg[_N];
vector<pair<int, int>> e[_N];
bool flag[_N];
signed main() {
    freopen("shortest10.in", "r", stdin);
    freopen("shortest10.out", "w", stdout);
    cin.tie(0)->sync_with_stdio(0);
    cin >> N >> M >> K;
    fill(flag + 1, flag + M + 1, 1);
    for (int i = 1; i <= M; ++i) {
        int x, y, w; cin >> x >> y >> w;
        e[x].emplace_back(y, i), e[y].emplace_back(x, i);
        ++deg[x], ++deg[y];
    }
    map<int, int> mp;
    vector<int> vec;
    for (int i = 1; i <= N; ++i) if (deg[i] > 2) {
        for (auto [v, id]: e[i]) if (deg[v] > 2 && i < v)
            vec.emplace_back(id), flag[id] = 0;
    }
    auto check = [&]()->bool {
        int d = 0;
        vector<bool> vis(N + 1, 0);
        auto dfs = [&](const auto &dfs, int x, int dep)->void {
            if (x == N) d = dep;
            vis[x] = 1;
            for (auto [v, id]: e[x]) if (flag[id] && !vis[v])
                dfs(dfs, v, dep + 1);
        };
        dfs(dfs, 1, 1);
        return d == N;
    };
    for (int x: vec) {
        flag[x] = 1;
        if (check()) break;
        flag[x] = 0;
    }
    vector<int> ans;
    for (int i = 1; i <= M; ++i) if (!flag[i])
        ans.emplace_back(i);
    cout << ans.size() << '\n';
    for (int x: ans) cout << x << '\n';
}

不得不说,写一道提答题感觉像是写了一整场模拟赛的暴力一样,一道题里面同时有很多个不同的问题。

标签:pre,dist,P4021,测试点,int,短路,vector,CTSC2012,id
From: https://www.cnblogs.com/hanx16msgr/p/17948113

相关文章

  • Bellman-Ford算法实现带有负权边的单源最短路
    Bellman-Ford算法对于Dijkstra算法,不妨给出这样一个例子graphLRA((A))-->|1|C((C))A-->|2|D((D))D-->|-4|C根据Dijkstra算法的流程,选取A为源点。更新与A邻接的顶点,有C和D。选取已更新顶点中距离A的最小值,显然选择边权为1的边所连接的顶点C,并将C收入最短路集合S中,此......
  • G. Bicycles 分层图单源最短路
    题目链接简单描述一下题意:给定n个点,m条带权无向边,每个点i有一辆速度系数为Si的自行车。每经过一个点即可拥有该点的自行车,在任意两点之间路过的消耗为:已经拥有的某辆自行车的速度Si*边权Wi,求从1号点到n号点的最小消耗。思路:因为需要求的是最小的总消耗,所以在某个点出发时,我......
  • Dijkstra实现单源最短路
    Dijkstra算法求单源最短路Dijkstra算法应用于求一个给定图的单个源点到其他各顶点的最短路。其中应用Dijkstra算法的图应满足如下条件图中没有负权边有向或者无向图都可以图中若有自环或者重边也可以(需要自己先筛选一下)Dijkstra算法的核心就是从源点开始对各个顶点进行......
  • 洛谷B3647 【模板】Floyd 题解 floyd算法 求 多源多汇最短路
    题目链接:https://www.luogu.com.cn/problem/B3647floyd算法:https://oi-wiki.org/graph/shortest-path/#floyd-算法示例程序:#include<bits/stdc++.h>usingnamespacestd;constintmaxn=101;intn,m,f[maxn][maxn];intmain(){scanf("%d%d",&n......
  • P1339 [USACO09OCT] Heat Wave G 最短路入门题 Dijkstra/SPFA/Dijkstra+优先队列优化
    目录朴素的Dijkstra算法SPFA算法Dijkstra+优先队列优化题目链接:https://www.luogu.com.cn/problem/P1339题目大意:无向图有单源最短路。朴素的Dijkstra算法时间复杂度\(O(n^2)\)。#include<bits/stdc++.h>usingnamespacestd;constintmaxn=2505;structEdge......
  • 最短路计数
    前置知识最短路的一个很好的性质:从\(s\)到\(t\)的最短路上的一个节点\(k\),都满足\(s\)到\(k\)的路径是关于\(s\)单源最短路的最短路证明:反证法,假设\(s\)到\(k\)的路径不为最短路,但\(s\tok\tot\)为到\(t\)的最短路,那么\(s\tok\tot\)的路径一定不会比\(s\)到\(k\)的最......
  • 7-5 单源最短路径
    7-5单源最短路径请编写程序求给定正权有向图的单源最短路径长度。图中包含n个顶点,编号为0至n-1,以顶点0作为源点。输入格式:输入第一行为两个正整数n和e,分别表示图的顶点数和边数,其中n不超过20000,e不超过1000。接下来e行表示每条边的信息,每行为3个非负整数a、b、c,其中a和b表示......
  • 图论——最短路
    https://csacademy.com/app/graph_editor/https://riverhamster.gitee.io/app/graph_editor/注:时间复杂度分析中,假设\(n\lem\len^2\)最短路本质上是一种DP阶段:点状态:拆点决策:边最优子结构:最短路的任何子路径都一定是最短路无后效性:正权图中一定可以找到一种无后......
  • 使用OCCT构建两个面之间的最短路径
    查找两个面之间的最短面路径查找面的邻面。std::vector<TopoDS_Face>OCCTUtility::adjacentFace(TopoDS_Faceconst&face,std::optional<TopoDS_Shape>shape,std::optional<TopTools_IndexedDataMapOfShapeListOfShape>edgeMapFace){std::vector<TopoD......
  • dijkstra最短路
    给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环,所有边权均为正值。请你求出 1 号点到 n 号点的最短距离,如果无法从 1 号点走到 n 号点,则输出 −1。输入格式第一行包含整数 n 和 m。接下来 m行每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y的......