最简单的最短路径
上代码……
dijkstra实现
#include<iostream>
using namespace std;
#define MAX 0x7fffffff
int map[1001][1001];
bool s[1001];
int d[1001];
int n,t;
int sum;
void dijkstra(int v)
{   
int a,b,c;
    
int i,j,k;
    
for(i=1;i<=n;i++)
    {   
for(j=1;j<=n;j++)
        {   map[i][j]
=MAX;
        }
    }
    
for(i=1;i<=t;i++)
    {   scanf(
"%d%d%d",&a,&b,&c);
        
if(c<map[a][b])
           map[a][b]
=map[b][a]=c;
    }
    
for(i=1;i<=n;i++)
        d[i]
=map[v][i];
    d[v]
=0;
    s[v]
=1;
    
for(i=1;i<n;i++)
    {    
int min=MAX;
         
for(j=1;j<n;j++)
         {   
             
if(!s[j]&&d[j]<min&&d[j]>0)
             {   k
=j;
                 min
=d[j];
             }
         }
         s[k]
=1;
         
for(j=1;j<=n;j++)
         {   
if(!s[j]&&d[k]+map[k][j]<d[j]&&map[k][j]<MAX)
             {   d[j]
=d[k]+map[k][j];
             }
         }
    }
}
int main()
{   
    scanf(
"%d%d",&t,&n);
    dijkstra(
1);
    printf(
"%d\n",d[n]);
    system(
"pause");
    
return 0;
    
}
spfa实现
#include<iostream>
using namespace std;
#define MAX 1001
#define maxx 0x7fffffff
int map[1001][1001];
int n,t;
int q[10*MAX];
int flag[MAX];
int d[MAX];
int spfa(int v)
{   memset(flag,
0,sizeof(flag)); 
    
int rear,front;
    
int now;
    
int i,j;
    
for(i=1;i<=n;i++)
       d[i]
=maxx;
    d[v]
=0;
    rear
=front=0;
    q[rear
++]=v;
    flag[v]
=1;

    
while(front<=rear)//队列不为空 
    {     
          now
=q[front++];
          flag[now]
=0;
          
for(i=1;i<=n;i++)
          {   
              
if(map[now][i]<maxx&&map[now][i]>0)
              {    
if(d[now]+map[now][i]<d[i])
                   {       d[i]
=d[now]+map[now][i];
                           
if(!flag[i])
                           {    flag[i]
=1;
                                q[rear
++]=i;
                           }
                   }
              }
          }
    }
    
return 0;
}
int main()
{   
int i,j;
    
int a,b,c;
    scanf(
"%d%d",&t,&n);
    
for(i=1;i<=n;i++)
    {   
for(j=1;j<=n;j++)
        {   map[i][j]
=maxx;
        }
    }
    
for(i=1;i<=t;i++)
    {   scanf(
"%d%d%d",&a,&b,&c);
        
if(c<map[a][b])
           map[a][b]
=map[b][a]=c;
    }
    spfa(
1);
    printf(
"%d\n",d[n]);
    system(
"pause");
    
return 0;
    
}

dijkstra用堆实现
#include<iostream>
using namespace std;
#define N 1001
#define MAX 0x7fffffff
int h[N];
int map[N][N];
int d[N];
int t,n;
int a,b,c;
int size;
void minheap(int i)
{    
int l=2*i;
     
int r=2*i+1;
     
int small=i;
     
if(l<=size&&d[h[i]]>d[h[l]])
     {   small
=l;
     }
     
if(r<=size&&d[h[small]]>d[h[r]])
     {  small
=r;
     }
     
if(small!=i)
     {   
int tmp=h[i];
         h[i]
=h[small];
         h[small]
=tmp;
         minheap(small);
     }
}
void build()
{   
int i;
    size
=n;
    
for(i=1;i<=size;i++)
       h[i]
=i;
    
for(i=(size>>1);i>=1;i--)
    {   minheap(i);
    }
}
int minsolve()
{   
    
int minn=h[1];
    h[
1]=h[size];
    size
--;
    minheap(
1);
    
return minn;
}
void de(int i,int key)
{   
    d[h[i]]
=key;
    
while(d[h[i]]<d[h[i/2]]&&i>1)
    {   
        
int tmp=h[i];
        h[i]
=h[i/2];
        h[i
/2]=tmp;
        i
/=2;
    }
    
}
void solve(int v)
{    
     
int i,j;
     
for(i=1;i<=n;i++)
     {    d[i]
=MAX;
     }
     d[v]
=0;
     build();
     
while(size>=1)
     {   
int u=minsolve();
         
for(i=1;i<=size;i++)
         {  
if(map[u][h[i]]<MAX&&d[u]+map[u][h[i]]<d[h[i]])
            {    de(i,d[u]
+map[u][h[i]]);
            }  
         }
     }
}
int main()
{   scanf(
"%d%d",&t,&n);
    
int i,j;
    
for(i=1;i<=n;i++)
    {   
        
for(j=1;j<=n;j++)
        {   
            map[i][j]
=MAX;
        }
    }
    
for(i=1;i<=t;i++)
    { 
         scanf(
"%d%d%d",&a,&b,&c);
         
if(c<map[a][b])
            map[a][b]
=map[b][a]=c;
         
    }
    solve(
1);
    printf(
"%d\n",d[n]);
    system(
"pause");
    
return 0;
}