AtCoderBeginnerContestAT_abc395_eABC395EFlipEdge题解

题目大意

有向图最短路，可以花钱反转所有边。

思路

注：为了与代码呼应，本文用 K K K 代替原题面中的 X X X，如有不便敬请谅解。

数据范围： N , M ≤ 2 × 1 0 5 N,M \le 2\times 10^5 N,M≤2×105，Dijkstra 能过。

读入：正反边存一个图，标注清楚。

记录当前点： ( x , t ) (x,t) (x,t)。其中 x x x 是节点编号， t = 1 t=1 t=1 时这个点是从正向边过来的， t = 2 t=2 t=2 时相反。每一次，要么顺着 t t t 的方向走（花费 1 1 1 日元），要么反之（花费 K + 1 K+1 K+1 日元，反转费 + 走路费）。

代码实现

Submission #63274095

#include <cstdio> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <cstring> using namespace std; int n, m, k; long long dis[200010][10]; int vis[200010][10]; struct edge { int y, t; } ; vector<edge> g[200010]; struct node { int x, t; long long d; bool operator < (const node & b) const { return d > b.d; } } ; void dijkstra(int s) { priority_queue<node> q; memset(dis, 0x3f, sizeof(dis)); memset(vis, 0, sizeof(vis)); q.push((node){s, 1, 0}); dis[s][1] = 0; while (q.size()) { int x = q.top().x; int t = q.top().t; q.pop(); if (vis[x][t]) continue; vis[x][t] = 1; for (int i = 0; i < g[x].size(); i++) { int y = g[x][i].y, tt = g[x][i].t; int w = 1; if (tt != t) w += k; if (dis[y][tt] > dis[x][t] + w) { dis[y][tt] = dis[x][t] + w; q.push((node){y, tt, dis[y][tt]}); } } } } int main() { cin >> n >> m >> k; for (int i = 1; i <= m; i++) { int x, y; cin >> x >> y; g[x].push_back((edge){y, 1}); g[y].push_back((edge){x, 2}); } dijkstra(1); cout << min(dis[n][1], dis[n][2]) << endl; return 0; } // 思维难度比 D 低，细节也少，难度大概是黄题