1988 Problem E 最短路徑問題

問題 E: 最短路徑問題

時間限制: 1 Sec  記憶體限制: 32 MB

送出: 61  解決: 31

題目描述

給你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 <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=1010;
const int INF=0x3fffffff;
bool inq[maxn];
int n,d[maxn],c[maxn],num[maxn];
struct node
{
    int v,w,c;
    node(int x,int y,int z):v(x),w(y),c(z){};
};
vector<node> adj[maxn];
bool SPFA(int s)
{
    fill(d,d+maxn,INF);
    memset(inq,0,sizeof(inq));
    memset(num,0,sizeof(num));
    fill(c,c+maxn,INF);
    queue<int> q;
    q.push(s);
    inq[s]=true;
    ++num[s];
    d[s]=0;
    c[s]=0;
    while(q.size())
    {
        int u=q.front();
        q.pop();
        inq[u]=false;
        for(int i=0;i<adj[u].size();++i)
        {
            int v=adj[u][i].v;
            int w=adj[u][i].w;
            int t=adj[u][i].c;
            if(d[u]+w<d[v])
            {
                d[v]=d[u]+w;
                c[v]=c[u]+t;
                if(!inq[v])
                {
                    q.push(v);
                    inq[v]=true;
                    ++num[v];
                    if(num[v]>=n)
                        return false;
                }
            }
            else if(d[u]+w==d[v])
            {
                if(c[u]+t<c[v])
                {
                    c[v]=c[u]+t;
                }
                
            }
        }
    }
    return true;
}
int main()
{
    int m,s,t,d1,d2,w,co;
    while(~scanf("%d %d",&n,&m))
    {
        if(n==0)
            break;
        for(int i=1;i<=n;++i)
            adj[i].clear();
        for(int i=0;i<m;++i)
        {
            scanf("%d %d %d %d",&d1,&d2,&w,&co);
            adj[d1].push_back(node(d2,w,co));
            adj[d2].push_back(node(d1,w,co));
        }
        scanf("%d %d",&s,&t);
        SPFA(s);
        printf("%d %d\n",d[t],c[t]);
    }
    return 0;
}