Graph&&北邮比赛题

最短路径题。。dijstra。。

#include<iostream>
#include<string.h>
#include<algorithm>
#include<limits.h>
#define M 0xffffff
#define N 500
#define  FOR(i,s,t) for(int i=(s);i<=t;++i)
using namespace std;
int dist[N];
int map[N][N];
bool visit[N];
int m,n,p,q;
void  Dijstra( )
{     cin>>p>>q ;
     FOR(i,0,n-1)
        { dist[i]=M;
          visit[i]=true;
        }
    dist[p]=0;
    visit[p]=false;
    FOR(i,0,n-1)
    {   FOR(j,0,n-1)
        if(visit[j]&&dist[j]>dist[p]+map[p][j])
          dist[j]=dist[p]+map[p][j];
          int minx=M;
          FOR(j,0,n-1)
          if(visit[j]&&dist[j]<minx)
           minx=dist[p=j];
           visit[p]=false;
           if(minx==M) break;
      }
      if(dist[q]==M) cout<<"-1"<<endl;
        else  cout<<dist[q]<<endl;
      }
int main()
{ int T;
  scanf("%d",&T);
  for(int cas=1;cas<=T;++cas)
  { 
	  scanf("%d%d",&n,&m);
	 for(int i=0;i<n;++i)
		for(int j=0;j<n;++j)
			if(i==j) map[i][j]=0;
			else  map[i][j]=map[j][i]=M;
	for(int i=0;i<m;++i)
	{   int a,b;
	   scanf("%d%d",&a,&b);
	    for(int k=0;k!=b;++k)
		{ int x,y,z;
		  scanf("%d%d%d",&x,&y,&z);
		  if(map[x][y]>z)
			  map[x][y]=map[y][x]=z;
		}
	}
	int ss;
	 scanf("%d",&ss);
	 char ch[10];
	 printf("Case :%d\n",cas);
	 while(ss--)
	 {  scanf("%s",ch);
	 if(ch[0]=='a')
	 {  int x,y,z;
	 scanf("%d%d%d",&x,&y,&z);
	  if(map[x][y]>z)
	 map[x][y]=map[y][x]=z;
     }
	 else  Dijstra( );
	 }
  }return 0;
}