一句话题意：给你一张有向有环图，成环各点间距为0，求点1到点n的最短路。
前置技能：tarjan（缩点）+最短路算法
然后，这道题就没了。
此题只需要先用tarjan找到所有的环，进行缩点后跑一遍dijkstra即可。
Code：
#include#include #include #include #include using namespace std;//Mystery_Sky//#define maxn 1000010#define maxm 5000050#define INF 0x3f3f3f3fstack st;struct Edge { int to, next, w;}edge[maxn];int head[maxn], cnt, n, m;int low[maxn], dfn[maxn], col[maxn], vis[maxn];int dis[maxn], vis1[maxn];int scc, tot, ans;inline void add_edge(int u, int v, int w){ edge[++cnt].to = v; edge[cnt].w = w; edge[cnt].next = head[u]; head[u] = cnt;}void Tarjan(int u){ low[u] = dfn[u] = ++tot; st.push(u); vis[u] = 1; for(int i = head[u]; i; i = edge[i].next) { int v = edge[i].to; if(!dfn[v]) { Tarjan(v); low[u] = min(low[u], low[v]); } else if(vis[v]) low[u] = min(low[u], dfn[v]); } if(dfn[u] == low[u]) { scc++; int j; do { j = st.top(); st.pop(); col[j] = u; vis[j] = 0; } while(j != u); }}struct node{ int dis; int pos; inline bool operator <(const node &x) const { return x.dis < dis; }};priority_queue q;inline void dijkstra(){ dis[1] = 0; q.push((node) {0, 1}); while(!q.empty()) { node top = q.top(); q.pop(); int x = top.pos; if(vis1[x]) continue; vis1[x] = 1; for(int i = head[x]; i; i = edge[i].next) { int y = edge[i].to; if(col[y] == col[x]) edge[i].w = 0; if(dis[y] > dis[x] + edge[i].w) { dis[y] = dis[x] + edge[i].w; if(!vis1[y]) q.push((node) {dis[y], y}); } } }}int main() { memset(dis, INF, sizeof(dis)); scanf("%d%d", &n, &m); int u, v, w; for(int i = 1; i <= m; i++) { scanf("%d%d%d", &u, &v, &w); add_edge(u, v, w); } for(int i = 1; i <= n; i++) if(!dfn[i]) Tarjan(i); dijkstra(); ans = dis[n]; printf("%d\n", ans);}