原帖及讨论：http://bbs.bccn.net/thread-226799-1-1.html

第一次发帖..不知道这个对大家有没有用...
PS:程序是在数学建模时写的...自己比较懒,所以改了别了的主要部分..输入主要是按建模时的要求..
/*
输入要求:第一个数为顶点总数,第二个为边的总数.
以下分别是一行三个数的"顶点,顶点,权值"
所有边的下一行为要求顶点到顶点最小路径的总数.
再以下几行,就为要求的顶点.
例:
4  4
1 2 2
1 4 4
2 3 4
3 4 2
2
1 3
2 4
*/
#include  <iomanip>
#include <iostream>
#include <cstdlib>
#include<fstream>
using namespace std;

struct Node
{
    int fr;
    int to;
    double weight;
    struct Node *next;

};//邻接表的简单结构体.
void Dijkstra(int n,int v,double dist[],double prev[],double **c)
{
    double maxint = 65535.0;
    int i,j;
    bool *s = new bool[n];
    for (  i = 1; i <= n; i++)
    {
        dist[i] = c[v][i];
        s[i] = false;
        if (dist[i] == maxint)
        {
            prev[i] = 0;
        }
        else
        {
            prev[i] = v;
        }
    }
    dist[v] = 0;
    s[v] = true;
    for ( i = 1; i < n; i++)
    {
        double temp = maxint;
        int u = v;
        for (  j = 1; j <= n; j++)
        {
            if ((!s[j]) && (dist[j] < temp))
            {
                u = j;
                temp = dist[j];
            }
        }
        s[u] = true;
        for (  j = 1; j <= n; j++)
        {
            if ((!s[j]) && (c[u][j] < maxint))
            {
                double newdist = dist[u] + c[u][j];
                if (newdist < dist[j])
                {
                    dist[j] = newdist;
                    prev[j] = u;
                }
            }
        }
    }
}

int main()
{
    int n,v,u,sum;
    int q = 0;
    int i,j,t;
    int m;//n为顶点数,m为边数
    ifstream fin("input.txt",ios::in);
    if(!fin)
        cout<<"can't open input.txt";
    fin>>n>>m;
    Node *root=new Node;
    Node *p;
    fin>>root->fr;
    fin>>root->to;
    fin>>root->weight;
    root->next=NULL;
    p=root;
    while(m!=1)
    {
        Node *pp = new Node;
        pp->next=NULL;
        fin>>pp->fr;
        fin>>pp->to;
        fin>>pp->weight;
        
        p->next=pp;
        p=pp;
        m--;
        
    }//生成邻接表
    
    int *way = new int[n + 1];
    double **c = new double *[n + 1];
    for (  i = 1; i <= n; i++)
    {
        c[i] = new double[n + 1];
    }//生成二维动态数组
   for (  j = 1; j <= n; j++)
    {
        for (  t = 1; t <= n; t++)
        {
            c[j][t]=65535.0;
         if(j==t)
        c[j][t]=0;
        }
    }//初始化二维数组
    Node *pt=root;
    while(pt)
    {    c[pt->fr][pt->to]=pt->weight;
        c[pt->to][pt->fr]=pt->weight;
        pt=pt->next;

    }//邻接表到邻接矩阵的转换
    ofstream fout("output.txt",ios::out);
    double *dist = new double [n+1];
    double *prev = new double [n+1]; //申请空间不足时可以通过DEBUG,但会崩溃 .所以为[n+1]
    fin>>sum;

    while(sum)
    {
    fin>>v>>u;
    Dijkstra(n, v, dist, prev, c);   
    int w = u;
    q=0;
    while (w != v)
    {
        q++;
        way[q] = prev[w];
        w = prev[w];
    }
    fout <<"最短路径从" <<v <<" -> " <<u ;
    fout <<"路径为：";
    for ( j = q; j >= 1; j--)
    {
        fout <<way[j] <<" ->";
    }
    fout <<u <<endl;
    fout<<" 费用:" <<showpoint<<dist[u] <<endl;
    --sum;
    } //end while
    delete  []way;
      for ( i = 1; i <= n; i++)
          delete []c[i];
      delete []c;
      delete []dist;     
      delete []prev;
  
    return 0;
} //申请空间不足时可以通过DEBUG,但会崩溃..原因是申请空间太少了.所以