POJ - 1847 Tram 最短路，思维建图

本文主要是介绍POJ - 1847 Tram 最短路，思维建图，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

POJ-1847

题意

给定n节点，节点之间有道路相连，但是每个节点都有个开关，只有开关指向的节点才能通行，你可以搬动开关。给定起点终点，求最少搬动开关次数。

解法

建图，对于每个节点，初始开关对准的节点连边，权值为0，代表经过这个边不需要动开关。对于其他链接的节点连边，权值为1，代表经过这个边需要动开关。跑一遍起点到终点最短路，dis数组求出来的就是最少搬动开关次数。

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>  
#include<cmath>
#include<cstdio>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
using namespace std;typedef long long ll;const int maxn=550;const int maxe=5050;const int inf=0x3f3f3f3f;struct Edge{int v,w,next;}edge[maxe];int head[maxn],cnt;bool vis[maxn];int in[maxn];int dis[maxn];int n,m;void init(){memset(head,-1,sizeof(head));cnt=0;}void add(int u,int v,int w){edge[cnt].v=v;edge[cnt].next=head[u];edge[cnt].w=w;head[u]=cnt;cnt++;}bool spfa(int s) {memset(vis,0,sizeof(vis));memset(in,0,sizeof(in));memset(dis,0x3f,sizeof(dis));queue<int>q;q.push(s);vis[s]=true;in[s]++;dis[s]=0;while(q.size()) {int p=q.front();q.pop();vis[p]=false;for(int i=head[p];i!=-1;i=edge[i].next) { //SPFAint v=edge[i].v;if(dis[v]>edge[i].w+dis[p]) {dis[v]=edge[i].w+dis[p];in[v]++;if(in[v]>=n)return true;//这个点更新了多于n次，说明存在负环 if(!vis[v]) {vis[v]=true;q.push(v);}}}}return false;}int main(){IOSinit();int s,t;cin>>n>>s>>t;for(int i=1;i<=n;i++){int tmp,v;cin>>tmp;if(!tmp)continue;tmp--;cin>>v;add(i,v,0);while(tmp--){cin>>v;add(i,v,1);}}spfa(s);if(dis[t]!=inf)cout<<dis[t]<<endl;elsecout<<"-1"<<endl;}