九度 1411 -图最短路径 - 转圈

本文主要是介绍九度 1411 -图最短路径 - 转圈，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这道题目检查对于dijkstra算法的掌握，如果对于这个算法有疑问的，可以看看这个博客点击打开链接，基本上已经讲得很清楚了。

这道题目的细节有:1：在给的有向图中，一条边会重复，所以我们要选最小的那条覆盖 2:有s-s的边。大家做的时候要小心这两个细节。

dijkstra算法代码整体模板就是这个博客点击打开链接的。

#include<iostream>
#include<string.h>
#define MAX 10000000
using namespace std;
int map[510][510];
int sp[510];
int s[510];int n,x,y;
void djs(){for(int i=1;i<=n;i++){sp[i]=MAX;s[i]=0;}int init=x,count=0;int mv,mi;for(int i=1;i<=n;i++){if(map[x][i]<sp[i])sp[i]=map[x][i];}while(count++<=n){mv=MAX+1, mi=-1;for(int i=1;i<=n;i++){if(!s[i]){if(map[init][i]+sp[init]<sp[i])sp[i]=map[init][i]+sp[init];if(sp[i]<mv){mv=sp[i];mi=i;}   }}s[mi]=1;init=mi;}if(sp[x]==MAX){cout<<"help!"<<endl;}else{cout<<sp[x]<<endl;}
}
int main(){int m;int a,b,t;while(cin>>n>>m>>x){memset(map,1,sizeof(map));for(int i=0;i<m;i++){cin>>a>>b>>t;map[a][b]=min(t,map[a][b]);}djs();}
}

这篇关于九度 1411 -图最短路径 - 转圈的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---