POJ-1847 Tram（水题意费劲！！！）

68 阅读 0 评论 45 点赞

我是靠谱客的博主顺心战斗机，最近开发中收集的这篇文章主要介绍POJ-1847 Tram（水题意费劲！！！），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

呐，给你的破题目——>破oj

题目本质来说是个水题，不仅数据范围小，而且还没什么多的处理。主要是这个输入方式，成功提高了这题的格调！！！

废话不多说，解释一下题意：：n个点嘛，然后同时n个边嘛。然后求a到b的最小改变方向的次数嘛。

！！！然后给了奇奇怪怪的

n是3，2是a 1是b 这个说过了。

第一行从第1个头点出发 2：接下来有两个尾点。2：第一个尾点2（直接到达）。3：第二个尾点3，要改变方向才能到。

所以意思就是 1->2 可以直接到达，1->3要改变方向才能到

第二行从第2个头点出发 2：接下来有两个尾点。3：第一个尾点3（直接到达）。1：第二个尾点1，要改变方向才能到。

所以意思就是 2->3 可以直接到达，2->1要改变方向才能到

第三行从第3个头点出发 2：接下来有两个尾点。1：第一个尾点1（直接到达）。2：第二个尾点2，要改变方向才能到。

所以意思就是 3->1 可以直接到达，3->2要改变方向才能到

然后自己想吧。

翻了很多博客，不是给代码就是讲思路，就没人看不懂题目？？？全都是看懂了题目了的？？？（脸黑）

对，我菜。不劳各位大佬动嘴了。

思路：要改方向的路径权值为1，直接到的0，到不了的inf，数据小，想用哪种用哪种。不嫌麻烦的话。

代码：我不想贴的，但是强迫症，不贴感觉怪怪的

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
#define inf 0x3f3f3f3f
#define mx 200
int n,A,B;
int e[mx][mx];
int main()
{
scanf("%d%d%d",&n,&A,&B);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
e[i][j]=i==j?0:inf;
for(int i=1;i<=n;i++)
{
int k,v;
scanf("%d",&k);
for(int j=0;j<k;j++)
{
scanf("%d",&v);
e[i][v]=j==0?0:1;
}
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
e[i][j]=min(e[i][j],e[i][k]+e[k][j]);
e[A][B]=e[A][B]==inf?-1:e[A][B];
printf("%dn",e[A][B]);
return 0;
}

补充一下spfa的写法：

写完之后没有调用spfa函数，一直不知道错哪。。。直到发现没调用的时候我的内心是崩溃的。

然后交了一发，wa了可是没毛病，然后想是不是数组开小了（原来开的200）然后我改成1000 AC了？？？为啥不RE？

#include<stdio.h>//spfa
#include<queue>
#include<string.h>
#include<algorithm>
using namespace std;
#define mx 1000//只要不炸，尽管开大
#define inf 0x3f3f3f3f
int n,a,b;
int head[mx];
int dis[mx];
bool vis[mx];
struct node
{
int v;
int w;
int next;
} adj[mx];
void spfa()
{
queue<int> q;
for(int i=1; i<=n; i++)
dis[i]=inf;
dis[a]=0;
q.push(a);
vis[a]=false;
while(!q.empty())
{
int now=q.front();
q.pop();
vis[now]=false;
for(int i=head[now]; i!=-1; i=adj[i].next)
{
int to=adj[i].v;
if(dis[to]>dis[now]+adj[i].w)
{
dis[to]=dis[now]+adj[i].w;
if(!vis[to])
{
vis[to]=true;
q.push(to);
}
}
}
}
}
int main()
{
int cnt=0,k;
memset(head,-1,sizeof(head));
scanf("%d%d%d",&n,&a,&b);
for(int i=1; i<=n; i++)
{
scanf("%d",&k);
for(int j=0; j<k; j++)
{
int to;
scanf("%d",&to);
adj[cnt].v=to;
adj[cnt].w=j==0?0:1;
adj[cnt].next=head[i];
head[i]=cnt++;
}
}
spfa();//记得调用啊，大兄弟！
printf("%dn",dis[b]=dis[b]==inf?-1:dis[b]);
return 0;
}

ps：题目题意都不知道，哪来的思路？？？怎么写代码？