Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：n点。。点i到点j的代价是|i-j|..给出n条近路。。。a[i]表示点i到a[i]的代价为1（注意近路不一定就近）
思路：一开始建边卡了一下。。。实际上只要连相邻的就好了。。。然后边表只开了2N蠢哭。。。实际上应该3M…因为连相邻的边是双向的。。。再加上近路的单向。。。然后spfa就好了。。。。
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2016年07月18日 星期一 13时33分18秒
4File Name :code/2016whust/F.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=2E5+7;
34int n;
35int a[N];
36bool inq[N];
37int d[N];
38int head[N];
39int cnt;
40
41
42struct Edge
43{
44 int v;
45 int w;
46 int nxt;
47}edge[8*N];
48
49void addedge( int u,int v,int w)
50{
51 edge[cnt].v = v;
52 edge[cnt].w = w;
53 edge[cnt].nxt = head[u];
54 head[u] = cnt;
55 cnt++;
56}
57void init()
58{
59 ms(head,-1);
60 cnt = 0 ;
61}
62void spfa( int s)
63{
64 ms(inq,false);
65 ms(d,0x3f);
66 queue<int>q;
67 q.push(s);
68 inq[s] = true;
69 d[s] = 0;
70
71 while (!q.empty())
72 {
73 int u = q.front();
74//< cout<<"u:"<<u<<endl;
75 q.pop();
76 inq[u] = false;
77
78 for ( int i = head[u] ; i!=-1 ; i = edge[i].nxt)
79 {
80 int v = edge[i].v;
81 int w = edge[i].w;
82 if (d[v]>d[u]+w)
83 {
84 d[v] = d[u] + w;
85 if (inq[v]) continue;
86 inq[v] = true;
87 q.push(v);
88 }
89// if (a[u]==v&&d[v]>1)
90// {
91// d[v] = 1;
92// if (inq[v]) continue;
93// inq[v] = true;
94// q.push(v);
95// }
96
97 }
98 }
99}
100int main()
101{
102 #ifndef ONLINE_JUDGE
103 freopen("code/in.txt","r",stdin);
104 #endif
105
106 cin>>n;
107 init();
108 for ( int i = 1 ; i <= n ; i++)
109 {
110 scanf("%d",&a[i]);
111 if (a[i]!=i)
112 addedge(i,a[i],1);
113// addedge(1,i,i-1);
114// addedge(i,1,i-1);
115// else addedge(i,a[i],0);
116 }
117 for ( int i = 1; i <= n-1 ; i++)
118 {
119 addedge(i,i+1,1);
120 addedge(i+1,i,1);
121 }
122
123 spfa(1);
124
125 for ( int i = 1 ; i <= n ; i++) printf("%d ",d[i]);
126
127
128 #ifndef ONLINE_JUDGE
129 fclose(stdin);
130 #endif
131 return 0;
132}