#include<iostream.h>
#include<memory.h>
int ga[1001][1001],dist[1001];
const int maxvalue=32767;
int vexn,edgen;
void create1(int n,int e)
{
  int i,j,k,w;
  for(i=1;i<=n;i++)
    for(j=1;j<=n;j++){
      if(i==j)ga[i][j]=0;
      else ga[i][j]=maxvalue;
    }
  for(k=1;k<=e;k++){
    cin>>i>>j>>w;
    if(ga[i][j]==maxvalue)ga[i][j]=ga[j][i]=w;
    else if(w<ga[i][j])ga[i][j]=ga[j][i]=w;
      }
}
void dijkstra(int i,int n)
{
  int j,k,w,m;
  int *s=new int[n+1];
  for(j=1;j<=n;j++){
    if(j==i)s[j]=1;else s[j]=0;
    dist[j]=ga[i][j];
  }
  for(k=1;k<=n-2;k++){
    w=maxvalue;m=i;
    for(j=1;j<=n;j++)
      if(s[j]==0&&dist[j]<w)
      {w=dist[j];m=j;}
    if(m!=i)s[m]=1;else break;
    for(j=1;j<=n;j++)
      if(s[j]==0&&dist[m]+ga[m][j]<dist[j]){
	dist[j]=dist[m]+ga[m][j];
      } 
  }

}
int main()
{
    int i,j;
    cin>>vexn>>edgen;
    memset(dist,0,sizeof(dist));
    create1(vexn,edgen);
    dijkstra(1,vexn);
    cout<<dist[vexn]<<endl;
    return 0;
}    

• Re:第一次试用dijkstra算法，不知错在那里，请高手指点 (39) tyl387 2009-02-13 13:29:40