首页 > 代码库 > codeforces 689B Mike and Shortcuts 最短路
codeforces 689B Mike and Shortcuts 最短路
题目大意:给出n个点,两点间的常规路为双向路,路长为两点之间的差的绝对值,第二行为捷径,捷径为单向路(第i个点到ai点),距离为1。问1到各个点之间的最短距离。
题目思路:SPFA求最短路
#include<iostream> #include<algorithm> #include<cstring> #include<vector> #include<stdio.h> #include<stdlib.h> #include<queue> #include<math.h> #include<map> #define INF 0x3f3f3f3f #define MAX 1000005 #define Temp 1000000000 #define MOD 1000000007 using namespace std; int a[MAX],vis[MAX],dist[MAX],n,k; struct node { int u,v,w,next; }G[MAX]; void Add(int u,int v,int w) { G[k].u=u; G[k].v=v; G[k].w=w; G[k].next=a[u]; a[u]=k++; } void SPFA() { queue<int>Q; int st=1; vis[1]=1; dist[1]=0; Q.push(st); while(!Q.empty()) { st=Q.front(); Q.pop(); vis[st]=0; for(int i=a[st];i!=-1;i=G[i].next) { int v=G[i].v; if(dist[v] > dist[st]+G[i].w) { dist[v]=dist[st]+G[i].w; if(!vis[v]) { vis[v]=1; Q.push(v); } } } } } int main() { int q; while(scanf("%d",&n)!=EOF) { k=0; memset(a,-1,sizeof(a)); memset(vis,0,sizeof(vis)); memset(dist,INF,sizeof(dist)); for(int i=1;i<=n;i++) { Add(i,i+1,1); Add(i+1,i,1); } for(int i=1;i<=n;i++) { scanf("%d",&q); Add(i,q,1); } SPFA(); for(int i=1;i<=n;i++) printf("%d%c",dist[i],i==n?‘\n‘:‘ ‘); } return 0; }
codeforces 689B Mike and Shortcuts 最短路
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。