新建 文本文档.txt

简单的floyd运用 第一行输入一个整数C。C是测试的情况（0< C <=30）.第二行一个正整数N( 0< N <=100),表示道路的总数.紧接N行

#include<stdio.h>
#include<algorithm>
#include<map>
#include<string>
using namespace std;
#define MAX 10000000///????????????
#define MP 210//????
int mapp[MP][MP],dist[MP],prev[MP];
map<string,int> my;
char s1[50];
char s2[50];
char h[50];
struct node
{
	int id;
	int len;
}point[MP];
int cmp(node x,node y)
{
	return x.len<y.len||(x.len==y.len&&x.id<y.id);
}
void dijkstra(int n,int st)//n--????????st--??????
{
	int min,now,i,j,newdist;
	bool used[MP];
	for(i=1;i<n;i++)
	{
		dist[i]=mapp[st][i];//????????????????????  ????????i ??????????????????
		used[i]=false;
	}
	dist[st]=0;//??????????????0
	used[st]=true;
	for(i=1;i<n;i++)//
	{
		min=MAX;
		now=st;
		for(j=1;j<n;j++)
		{
			if((!used[j])&&(dist[j]<min))//????st?? ????????
			{
				now=j;
				min=dist[j];
			}
		}
		used[now]=true;
		if(now==my[s2])
		{
			if(min==MAX)
				puts("-1");
			else
				printf("%d\n",min);
			return ;
		}
		for(j=1;j<n;j++)
		{
			if((!used[j])&&(mapp[now][j]<MAX))
			{
				newdist=dist[now]+mapp[now][j];//??????????????????????
				if(newdist<dist[j])
				{
					dist[j]=newdist;
					//	prev[j]=now;//??????????
				}
			}
		}
	}
	puts("-1");
}
int main()
{
	int i,j,n,m;
	int x,y,value,ncase;
	scanf("%d",&ncase);
	while(ncase--)
	{
		scanf("%d",&m);
		my.clear();
		int id=1;
		for(i=1;i<205;i++)
		{
			for(j=1;j<205;j++)
				mapp[i][j]=MAX;
			mapp[i][i]=0;
		}
		for(i=0;i<m;i++)
		{	
			scanf("%s%s%d",s1,s2,&value);
			if(my[s1]==0)
				my[s1]=id++;
			if(my[s2]==0)
				my[s2]=id++;
			mapp[my[s1]][my[s2]]=mapp[my[s2]][my[s1]]=value;			
		}
		scanf("%s%s",s1,s2);
if(strcmp(s1,s2)==0)
		{
			puts("0");
			continue;
		}

		if(my[s1]==0||my[s2]==0)
		{
			puts("-1");
			continue;
		}
				dijkstra(id,my[s1]);
	}
	return 0;
}