poj1502-dijs

一道求最短路径的最长边的题，本身没什么好说的。  很大的一个问题是在输入上面，怎么把字符串中的数字转换为整数  。

可以用C中的

int t =atoi(char *c)方法 
 discuss中也有人给出了另一种方法


if(scanf("%d",&m)!=0)
	map[i][j]=map[j][i]=m;
else
{
	map[i][j]=map[j][i]=INITMAX;
	scanf("x");
}

因为

scanf("%d%d",&a,&b);

如果a和b都被成功读入，那么scanf的返回值就是2

如果只有a被成功读入，返回值为1

如果a和b都未被成功读入，返回值为0

如果遇到错误或遇到end of file，返回值为EOF。

且返回值为int型.

 

下面贴代码

#include<iostream>
#include<cstdlib>
using namespace std;
#define MAXSIZE 110
#define INF 1000000
int map[MAXSIZE][MAXSIZE];
int vis[MAXSIZE];
int dis[MAXSIZE];
int n;

int dijs()
{
	int i,j;
	memset(vis,0,sizeof(vis));
	for(i=1;i<=n;i++)
	{
		if(map[1][i])
			dis[i]=map[1][i];
		else
			dis[i]=INF;
	}
	dis[1]=0;
	vis[1]=1;
	for(i=1;i<n;i++)
	{
		//find min
		int min=INF;
		int index=-1;
		for(j=1;j<=n;j++)
		{
			if(!vis[j]&&dis[j]<min)
			{
				min=dis[j];
				index=j;
			}
		}

		//update 
		if(index!=-1)
		{
			vis[index]=1;
			for(j=1;j<=n;j++)
			{
				if(!vis[j]&&map[index][j])
				if(dis[j]>dis[index]+map[index][j])
				{
					dis[j]=dis[index]+map[index][j];
				}
			}
		}
	}
	int ans=-1;
	for(j=1;j<=n;j++)
	{
		if(ans<dis[j])
			ans=dis[j];//=ans;
	}
	return ans;
}
int main()
{
	//freopen("in.txt","r",stdin);
	while(scanf("%d",&n)!=EOF)
	{
		int i,j;
		memset(map,0,sizeof(map));
		for(i=1;i<n;i++)
			for(j=1;j<=i;j++)
			{
				char t1[10];
				scanf("%s",&t1);
				if(t1[0]=='x')
					map[i+1][j]=map[j][i+1]=0;
				else
					map[i+1][j]=map[j][i+1]=atoi(t1);

			}
		printf("%d\n",dijs());
	}
}