nyoj 1006（最短路次短路）

偷西瓜

描述

對於農村的孩子來說最大的樂趣，莫過於和小伙伴們一塊下地偷西瓜了，雖然孩子們條件不是很好，但是往往他們很聰明，他們總在計算著到達瓜田的距離，以及逃跑的路線，他們總是以最短的距離沖到瓜田裡面，然後以最短的距離回到出發的地方，不過瓜田的大人們已經在他們來的路上等待他們。於是聰明的小伙伴們便不走過的路，即每條路只走一遍,如果小伙伴們回不到出發的地方，他們就說“eating”，

我們假設 有 n (n<=100)個 村莊 m條路(m<=1000)小伙伴們總是從1號村莊出發，而瓜田總是在n號村莊.如果小伙伴們到達不了n號村莊，或者回不到1號村莊請輸出"eating";

輸入

多組數據
第一行一個整數 n
第二行 一個整數 m
隨後的m行 有 三個數u,v,w 表示u 到 v村莊的距離為w(w<=1000);

輸出

求小伙伴們從1號村莊出發，到 n號村莊，再回到1號村莊所用的最短距離，如果不能回到1號村莊請輸出“eating”.

樣例輸入

2
1
1 2 999
3
3
1 3 10
2 1 20
3 2 50

樣例輸出

eating
80

上傳者

分析：求一個最短路和一個次短路的和。

那麼我們用spfa求一次從1到n的最短路，然後順便記錄路徑，然後求完之後把走過的路徑刪去。然後在求一次1到n的最短路。

spfa講解：http://blog.csdn.net/y990041769/article/details/18367665

代碼：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 300;
struct Point
{
    int x,y;
    int r;
    int num;
};
Point a[N];
struct Node
{
    int v,len;
};
vector map[N];
int n,m;
void spfa(int s,int dis[])
{
    int i,pre[N];
    bool used[N];
    queue q;
    memset(used,0,sizeof(used));
    memset(pre,-1,sizeof(pre));
    for(i=0; idis[u]+p.len)
            {
                dis[p.v]=dis[u]+p.len;
                pre[p.v]=u;
                if(!used[p.v])
                {
                    used[p.v]=true;
                    q.push(p.v);
                }
            }
        }
    }
    for(int i=n;pre[i]!=-1;i=pre[i])
    {
//        printf("%d ",pre[i]);
        for(int j=0;j=inf)
            printf("eating\n");
        else
            printf("%d\n",ans);
    }
    return 0;
}