hdu1874

#include<cstdlib>
#include<iostream>
#include<cstring>

using namespace std;

int mj[202][202];
int result[202];
int n,m;

void dij(int x)
{
 int j,flag[202],i,u,min;
 for(i=0;i<n;i++)
 {
  result[i]=mj[x][i];
  flag[i]=0;
 }
 flag[x]=1;
 result[x]=0;
 for(i=1;i<n;i++)
 {
  min=200005;
  for(j=0;j<n;j++)
   if(result[j]<=min&&flag[j]==0) {min=result[j];u=j;}
  flag[u]=1;
  for(j=0;j<n;j++)
  {
   if((result[j]>(min+mj[u][j]))&&flag[j]==0)
    result[j]=min+mj[u][j];
  }
 }

}

/*第一次做最短路径的题目，一次交就ac了
注意有重边输入，取最小的就ok了*/

int main()
{
 int x,y,z,t,i,j;
 while(scanf("%d %d",&n,&m)!=EOF)
 {
  for(i=0;i<n;i++)
   for(j=0;j<n;j++)
    mj[i][j]=200005;
  for(i=0;i<m;i++)
  {
   scanf("%d %d %d",&x,&y,&z);
   if(z<mj[x][y]) mj[x][y]=z;
   if(z<mj[y][x]) mj[y][x]=z;
  }
  scanf("%d %d",&x,&y);
  dij(x);
  if(result[y]<200005)
  printf("%d\n",result[y]);
  else
   printf("-1\n");

 }

 return 0;
}

本文出自 “Qero” 博客，请务必保留此出处http://8590696.blog.51cto.com/8580696/1358890

hdu1874

原文：http://8590696.blog.51cto.com/8580696/1358890