这题是个简单的Dijkstra问题。关键是在输入。我的那个输入方法是看discuss别人给出的。如不用这个的话我们可以把字符串转换为数字。还有就是它题目要求的是到所有节点d的最短路径中最大的那个cost!
#include <iostream> #include <fstream>using namespace std; #define LEN 101 #define INF (1<<30) #define MAX(a,b) (a>b?a:b)int n,dist[LEN]; int map[LEN][LEN],maxcost; bool v[LEN];void Dijkstra() {int i,j,min,min_pos;maxcost=0;for(i=1; i<=n; i++){dist[i]=map[1][i];}v[1]=true;for(i=1; i<n; i++) //n-1 {min=INF;for(j=2; j<=n; j++) //寻找最小的 {if(!v[j] && dist[j]<min){min=dist[j];min_pos=j;}}v[min_pos]=true;maxcost=MAX(maxcost,dist[min_pos]);for(j=1; j<=n; j++){if(!v[j] && dist[j]>dist[min_pos]+map[min_pos][j]){dist[j]=dist[min_pos]+map[min_pos][j];}}} }int main() {int i,j,temp;freopen("acm.txt","r",stdin);scanf("%d",&n);memset(v,false,sizeof(v));for(i=1; i<=n; i++){for(j=1; j<=i; j++){if(j==i){map[i][j]=0;}else if(scanf("%d",&temp)!=0)map[i][j]=map[j][i]=temp;else{map[i][j]=map[j][i]=INF;scanf("x");}}}Dijkstra();printf("%d\n",maxcost);return 0; }