题目：
Input
An edge-weighted graph G (V, E).
|V| |E| s0 t0 d0 s1 t1 d1 : s|E|-1 t|E|-1 d|E|-1
|V| is the number of vertices and |E| is the number of edges inG. The graph vertices are named with the numbers 0, 1,..., |V|-1 respectively.
si and ti represent source and target vertices ofi-th edge (directed) and di represents the cost of thei-th edge.
Output
If the graph contains a negative cycle (a cycle whose sum of edge costs is a negative value), print
NEGATIVE CYCLE
in a line.
Otherwise, print
D0,0 D0,1 ... D0,|V|-1 D1,0 D1,1 ... D1,|V|-1 : D|V|-1,0 D1,1 ... D|V|-1,|V|-1
The output consists of |V| lines. For each ith line, print the cost of the shortest path from vertexi to each vertex j (j = 0, 1, ... |V|-1) respectively. If there is no path from vertexi to vertex j, print "INF". Print a space between the costs.
Constraints
- 1 ≤ |V| ≤ 100
- 0 ≤ |E| ≤ 9900
- -2 × 107 ≤ di ≤ 2 × 107
- There are no parallel edges
- There are no self-loops
Sample Input 1
4 6 0 1 1 0 2 5 1 2 2 1 3 4 2 3 1 3 2 7
Sample Output 1
0 1 3 4 INF 0 2 3 INF INF 0 1 INF INF 7 0
Sample Input 2
4 6 0 1 1 0 2 -5 1 2 2 1 3 4 2 3 1 3 2 7
Sample Output 2
0 1 -5 -4 INF 0 2 3 INF INF 0 1 INF INF 7 0
Sample Input 3
4 6 0 1 1 0 2 5 1 2 2 1 3 4 2 3 1 3 2 -7
Sample Output 3
NEGATIVE CYCLE
题意：
首先输入有向带权图的点数v和边数e，接下来e行，每行输入三个数s，t，d，表示一条s到t的权为d的边。
若图中存在负环,则输出：NEGATIVE CYCLE。否则输出所有点对的最短路（矩阵）。
#include<bits/stdc++.h>typedef long long ll;using namespace std;const ll INF = 1LL<<32;int n,e;ll dp[110][110];void floyd(){for(int k = 0 ; k<n ; k++){for(int i = 0 ; i<n ; i++){if(dp[i][k] == INF)continue;for(int j = 0 ; j<n ; j++){if(dp[k][j] == INF)continue;dp[i][j] = min(dp[i][j] , dp[i][k]+dp[k][j]);}}}
}int main(){ios::sync_with_stdio(false);cin>>n>>e;for(int i = 0 ; i<n ; i++){for(int j = 0 ; j<n ; j++){if(i == j)dp[i][j] = 0;elsedp[i][j] = INF; }}for(int i = 0 ; i<e ; i++){int s,t,d;cin>>s>>t>>d;dp[s][t] = d;}floyd();bool flag = 0;for(int i = 0 ; i<n ; i++){if(dp[i][i] < 0){flag = 1;break;}}if(flag){cout<<"NEGATIVE CYCLE"<<endl;}else{for(int i = 0 ; i<n ; i++){for(int j = 0 ; j<n ; j++){if(j) cout<<" ";if(dp[i][j] == INF){cout<<"INF";}elsecout<<dp[i][j];}cout<<endl;}}return 0;
}