#include <iostream>
using namespace std;
int MAXNUM=10000;
int Arcs[51][51],dist[51],s[51],path[51];
void ShortestPath(int n,int v)
{
     int u,min;
     for(int i=1;i<=n;i++)
         for(int j=1;j<=n;j++)
             if(Arcs[i][j]==-1)
             {
                 Arcs[i][j]=MAXNUM;
             }
     for(int i=1;i<=n;i++)
     {
         dist[i]=Arcs[v][i];
         s[i]=0;
         if(dist!=0 && dist[i]<MAXNUM)
         {
             path[i]=v;
         }
         else
             path[i]=-1;
     }
     dist[v]=0;
     s[v]=1;
     for(int i=1;i<=n;i++)
     {
         min=MAXNUM;
         u=v;
         for(int j=1;j<=n;j++)
         if(!s[j] && dist[j]<min)
         {
             u=j;min=dist[j];
         }
         if(min==MAXNUM) return;
         s[u]=1;
         for(int w=1;w<=n;w++)
         if(!s[w] && min+Arcs[u][w]<dist[w])
         {
             dist[w]=min+Arcs[u][w];
             path[w]=u;
         }
     }
}
int main()
{
     int n,s,t,k=0;
     while(cin>>n)
     {
         for(int i=1;i<=n;i++)
             for(int j=1;j<=n;j++)
                 cin>>Arcs[i][j];
         cin>>s>>t;
         ShortestPath(n,s);
         cout<<"Case "<<++k<<endl;
         cout<<dist[t];
          cout<<endl;
     }
     return 0;
}

看了的请回帖,谢谢!

prim和这个都看过，当时偶花了3天把prim搞定了，这个至今不明真相，除非需要，不然肯定看不下去，话说这个算法其实很适合一些游戏...