九度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;  
}