#include <bits/stdc++.h> using namespace std; #define MAX 200 #define INF 0x7fffffff //下标从1开始 int graph[MAX + 1][MAX + 1], points[MAX + 1], m, n; //任意图,只要权值是正即可 //动态规划算法,取最小值时可以用堆(优先队列) //只能运算符重载 < 。。。。,好像是因为接口的原因。 struct data { int n, d; data(int n, int d) { this->d = d; this->n = n; } //注意 后面的const必须写 bool operator< (data const &a) const { return this->d>a.d; } }; void show_dj(int path[],int n,int source){ if(source==n){ cout<<n<<"->"; }else{ show_dj(path,path[n],source); cout<<n<<"->"; } } void dijkstra(int source) { //path 存前驱路径 int path[MAX + 1], ok[MAX + 1],d[MAX+1];//d是距离,只存不找 priority_queue<data,vector<data> > pq; memset(ok, 0, sizeof(ok)); ok[source]=1; for (int i = 1; i <= n; i++) { if(graph[source][i]<INF){ path[i] = source; d[i]=graph[source][i]; pq.push(data(i,graph[source][i])); }else { path[i] = i; d[i]=INF; } } //如果需要改动队列的内容,所以直接插入新的data,因为新的一定比旧的小, //所以肯定现出来,但是必须用ok判断一下 while(!pq.empty()){ data p=pq.top(); pq.pop(); if(ok[p.n]==1) continue; ok[p.n]=1; show_dj(path,p.n,source); cout<<endl; for(int i=1;i<=n;i++){ if(!ok[i]&&graph[p.n][i]<INF){ if(p.d+graph[p.n][i]<d[i]){ d[i]=p.d+graph[p.n][i]; path[i]=p.n; pq.push(data(i,d[i])); } } } } } int main() { cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) graph[i][j] = INF; for (int i = 1; i <= n; i++) points[i] = i; for (int i = 0; i < m; i++) { int x, y, z; cin >> x >> y >> z; graph[x][y] = z; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) cout << graph[i][j] << " "; cout << endl; } dijkstra(1); return 0; }