数学建模时写的..不知道有没有用...共享先..
/*
输入要求:第一个数为顶点总数,第二个为边的总数.
以下分别是一行三个数的"顶点,顶点,权值"
所有边的下一行为要求顶点到顶点最小路径的总数.
再以下几行,就为要求的顶点.
例:  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];
    double *prev = new double [n];
    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;
}

还是复杂