题解 | #单源最短路-Dijkstra算法#
单源最短路
https://www.nowcoder.com/practice/9f15b34a2a944a7798a5340ff0dba8b7
int findShortestPath(int n, int m, vector<vector<int> >& graph) {
vector<vector<int> >G(n,vector<int>(n,INT32_MAX));
//重边害死菜鸡本尊，两个顶点有多条有向边时，用短边
for(int i=0;i<m;i++)
G[(graph[i][0]-1)][(graph[i][1]-1)]=min(graph[i][2],G[(graph[i][0]-1)][(graph[i][1]-1)]);
for(int i=0;i<n;i++) G[i][i]=0;
vector<int> dist(n,INT32_MAX);
for(int i=0;i<n;i++) dist[i] = G[0][i];
for(int i=1;i<n;i++)
for(int j=1;j<n;j++)
if(dist[i]!=INT32_MAX&&G[i][j]!=INT32_MAX)
dist[j] = min(dist[j],dist[i]+G[i][j]);
//for(int i:dist) cout<<"dist[i]:"<<i<<endl;
return dist[n-1]==INT32_MAX?-1:dist[n-1];
// write code here
}
查看45道真题和解析