Luogu P1119 灾后重建【floyd】By cellur925

这道题我们很容易想到对于每次询问，都跑一遍最短路（spfa，虽然他已经死了）。只需在松弛的时候加入当前相关的点是否已经修好的判断，果不其然的TLE了4个点。

（然鹅我第一次用spfa跑的时候竟然全WA了，震惊！由于节点从0开始标号，所以head数组要预处理为-1，遍历的时候for(int i=head[x];i!=-1;i=edge[i].next啊啊啊啊啊）

Code_TLE

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<queue>
 5 
 6 using namespace std;
 7 const int inf=2147483647;
 8 
 9 int n,m,Q,tot;
10 int ddl[250],dis[250],head[250];
11 bool vis[250];
12 struct node{
13     int next,to,val;
14 }edge[32000];
15 
16 void add(int x,int y,int z)
17 {
18     edge[++tot].to=y;
19     edge[tot].val=z;
20     edge[tot].next=head[x];
21     head[x]=tot;
22 }
23 
24 int spfa_ask(int s,int t,int T)
25 {
26     memset(vis,0,sizeof(vis));
27     for(int i=0;i<n;i++) dis[i]=inf;
28     queue<int>q;
29     q.push(s);dis[s]=0;vis[s]=1;
30     while(!q.empty())
31     {
32         int x=q.front();
33         q.pop();vis[x]=0;
34         for(int i=head[x];i!=-1;i=edge[i].next)
35         {
36             int y=edge[i].to;
37             if(dis[y]>dis[x]+edge[i].val&&ddl[y]<=T&&ddl[x]<=T)
38             {
39                 dis[y]=dis[x]+edge[i].val;
40                 if(!vis[y]) q.push(y),vis[y]=1;
41             }
42         }
43     }
44     if(dis[t]==inf) dis[t]=-1;
45     return dis[t];
46 }
47 
48 int main()
49 {
50     memset(head,-1,sizeof(head));
51     scanf("%d%d",&n,&m);
52     for(int i=0;i<n;i++) scanf("%d",&ddl[i]);
53     for(int i=1;i<=m;i++)
54     {
55         int x=0,y=0,z=0;
56         scanf("%d%d%d",&x,&y,&z);
57         add(x,y,z);add(y,x,z);
58     }
59     scanf("%d",&Q);
60     while(Q--)
61     {
62         int x=0,y=0,T=0;
63         scanf("%d%d%d",&x,&y,&T);
64         printf("%d
",spfa_ask(x,y,T));
65     }
66     return 0;
67 }

View Code

万万没想到，正解竟然是--floyd!

其实看似繁琐的题目已经隐藏着真相--

本题的数据范围n<=200，这对于最短路题目来说是十分超常友善的：）也正暗喻着本题floyd才是正解。

正解：

我们考虑floyd的算法，本质是一个动态规划，最外层枚举中心点，注意到每次询问的时间有单调性，那么我们可以每次把两次询问间新建出的村庄的floyd跑好得出答案。

看题解在这卡了很久，结果发现自己忽略了一个条件：输入村庄的修复时间也是有单调性的，有了这个条件一切不就顺理成章了嘛。

Code

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 
 5 using namespace std;
 6 
 7 int n,m,Q,pos,limit;
 8 int ddl[300];
 9 int f[300][300];
10 
11 int main()
12 {
13     scanf("%d%d",&n,&m);
14     memset(f,0x3f,sizeof(f));
15     limit=f[3][3];
16     for(int i=0;i<n;i++) scanf("%d",&ddl[i]),f[i][i]=0;
17     for(int i=1;i<=m;i++)
18     {
19         int x=0,y=0,z=0;
20         scanf("%d%d%d",&x,&y,&z);
21         f[x][y]=z;f[y][x]=z;
22     }
23     scanf("%d",&Q);
24     while(Q--)
25     {
26         int x=0,y=0,t=0;
27         scanf("%d%d%d",&x,&y,&t);
28         if(ddl[x]>t||ddl[y]>t)
29         {
30             printf("-1
");
31             continue;
32         }
33         while(ddl[pos]<=t&&pos<n)
34         {
35             for(int i=0;i<n;i++)
36                 for(int j=0;j<n;j++)
37                     f[i][j]=min(f[i][j],f[i][pos]+f[pos][j]);
38             pos++;
39         }
40         if(f[x][y]==limit)
41         {
42             printf("-1
");
43             continue;
44         }
45         printf("%d
",f[x][y]);
46     }
47     return 0;
48 }

View Code

审题！审题！别丢条件！

Luogu P1119 灾后重建 【floyd】By cellur925

Luogu P1119 灾后重建【floyd】By cellur925