九度OnlineJudge之最短路径问题

解决：1004

题目描述：

给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。

输入：

输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点t。n和m为0时输入结束。

(1<n<=1000, 0<m<100000, s != t)

输出：

输出一行有两个数，最短距离及其花费。

样例输入：

3 2

1 2 5 6

2 3 4 5

1 3

0 0

样例输出：

9 11

#include <iostream>  
#include <vector>  
  
using namespace std;  
  
typedef struct E  
{  
    int next;  
    int c;  
    int cost;  
}E;  
  
bool mark[1001];  
  
int   dis[1001];  
  
int cost[1001];  
  
vector<E>  edge[1001];  
  
  
int main()  
{  
    int N,M;  
  
    while(cin>>N>>M)  
    {  
        if (N==0&&M==0)  break;  
        for (int i=1;i<=N;i++)  
        {  
            edge[i].clear();  
            dis[i] = -1;  
            mark[i] = false;  
            cost[i] = 0;  
        }  
        while(M--)  
        {  
            int  a,b,c,cost;  
  
            cin>>a>>b>>c>>cost;  
  
            E  T;  
  
            T.c = c;  
  
            T.cost = cost;  
      
            T.next = b;  
  
            edge[a].push_back(T);  
  
            T.next = a;  
  
            edge[b].push_back(T);  
        }  
        int S,D;  
        cin>>S>>D;  
  
        dis[S] =  0;  
  
        mark[S] = true;  
  
        int  newP = S;//起点为S,  
  
        for (int i=1;i<N;i++)  
        {  
            for (int j=0;j<edge[newP].size();j++)  
            {  
                E tmp = edge[newP][j];  
  
                int t = tmp.next;  
  
                int c = tmp.c;  
                  
                int co = tmp.cost;  
  
                if (mark[t]==true) continue;  
  
                if (dis[t]==-1 || dis[t] > dis[newP] +c || (dis[t]==dis[newP]+c) && (cost[t] >cost[newP] +co) )  
                {  
                    dis[t] = dis[newP] + c;  
  
                    cost[t] = cost[newP] +co;  
  
                }  
            }  
  
            int min=123123123;  
  
            for (int j=1;j<=N;j++)  
            {  
                if (mark[j]) continue;  
                if (dis[j]==-1) continue;  
                if (dis[j] < min)  
                {  
                    min = dis[j];  
                    newP = j;  
                }  
  
            }  
            mark[newP] = true;  
        }  
  
                  cout<<dis[D]<<" "<<cost[D]<<endl;  
  
    }  
  
      
  
    return 0;  
}

补充：软件开发 , C++ ,