首页编程题解

# 有负环最短路径 - 第十课：最短路径 -【中级班】517 编程普及组

# 描述

给定一个有向图，求 1 到 n 的最短路径。
可以判断图中是否有负环。

# 输入

第一行两个整数 n 和 m，表示点数和边数。
接下来 m 行，每行 3 个整数，表示一条有向边。

# 输出

如果图中有负环，输出 circle
如果没有负环，但是从 1 无法到达 n，输出 can’t arrive!
否则输出 1 到 n 的最短距离

# 样例

# 输入 #1

3 3
1 3 3
1 2 1
2 3 1

# 输出 #1

2

# 输入 #2

3 3
1 2 1
2 1 -2
2 3 1

# 输出 #2

circle

# 输入 #3

3 2
1 2 1
2 1 1

# 输出 #3

can't arrive!

# 提示

n≤200
m≤2000

# 思路

这题就是标准负环最短路

# 易错点

  1. 中转边必须有边才能转移： if(g[u][i]!=998244353&&g[i][v]!=998244353)
  2. g[u][v] 可以等于 998244353

# 代码

#include <bits/stdc++.h>
using namespace std;
int g[210][210];
int main() {
  int n,m;
  cin>>n>>m;
  for(int i=1; i<=n; i++) {
    for(int j=1; j<=n; j++) {
      if(i!=j) {
        g[i][j]=998244353;
      }
    }
  }
  int u,v,w;
  for(int i=1; i<=m; i++) {
    cin>>u>>v>>w;
    g[u][v]=min(w,g[u][v]);
  }
  for(int i=1; i<=n; i++) {
    for(int u=1; u<=n; u++) {
      for(int v=1; v<=n; v++) {
        if(g[u][i]!=998244353&&g[i][v]!=998244353) {
          if(g[u][i]+g[i][v]<g[u][v]) {
            g[u][v]=g[u][i]+g[i][v];
          }
        }
      }
      if(g[u][u]<0) {
        cout<<"circle"<<endl;
        return 0;
      }
    }
  }
  if(g[1][n]==998244353) {
    cout<<"can't arrive!\n";
  } else {
    cout<<g[1][n]<<"\n";
  }
  return 0;
}