偷西瓜
时间限制:1000 ms | 内存限制:65535 KB
难度:4
-
描述
-
对于农村的孩子来说最大的乐趣,莫过于和小伙伴们一块下地偷西瓜了,虽然孩子们条件不是很好,但是往往他们很聪明,他们总在计算着到达瓜田的距离,以及逃跑的路线,他们总是以最短的距离冲到瓜田里面,然后以最短的距离回到出发的地方,不过瓜田的大人们已经在他们来的路上等待他们。于是聪明的小伙伴们便不走过的路,即每条路只走一遍,如果小伙伴们回不到出发的地方,他们就说“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 <cstdio>
-
#include <vector>
-
#include <iostream>
-
#include <stack>
-
#include <cstdio>
-
#include <string>
-
#include <cstring>
-
#include <cmath>
-
#include <algorithm>
-
#include <queue>
-
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<Node> map[N];
-
int n,m;
-
void spfa(int s,int dis[])
-
{
-
int i,pre[N];
-
bool used[N];
-
queue<int> q;
-
memset(used,0,sizeof(used));
-
memset(pre,-1,sizeof(pre));
-
for(i=0; i<N; i++)
-
dis[i]=inf;
-
dis[s]=0;
-
used[s]=true;
-
q.push(s);
-
while(!q.empty())
-
{
-
int u=q.front();
-
q.pop();
-
used[u]=false;
-
for(i=0; i<map[u].size(); i++)
-
{
-
Node p=map[u][i];
-
if(dis[p.v]>dis[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])
-
{
-
-
for(int j=0;j<map[i].size();j++)
-
{
-
if(map[i][j].v==pre[i])
-
map[i].erase(map[i].begin()+j);
-
}
-
for(int j=0;j<map[pre[i]].size();j++)
-
{
-
if(map[pre[i]][j].v==i)
-
map[pre[i]].erase(map[pre[i]].begin()+j);
-
}
-
}
-
}
-
int main()
-
{
-
int dis1[N];
-
while(~scanf("%d%d",&n,&m))
-
{
-
for(int i=0;i<=n;i++)
-
map[i].clear();
-
for(int i=0;i<m;i++)
-
{
-
int x,y,z;
-
scanf("%d%d%d",&x,&y,&z);
-
Node tmp;
-
tmp.v=y,tmp.len=z;
-
map[x].push_back(tmp);
-
tmp.v=x;
-
map[y].push_back(tmp);
-
}
-
int ans=0;
-
spfa(1,dis1);
-
ans+=dis1[n];
-
spfa(1,dis1);
-
ans+=dis1[n];
-
if(ans>=inf)
-
printf("eating\n");
-
else
-
printf("%d\n",ans);
-
}
-
return 0;
-
}
nyoj1006(最短路次短路spfa),布布扣,bubuko.com
nyoj1006(最短路次短路spfa)
原文:http://blog.csdn.net/y990041769/article/details/25486099