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

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<queue>

 using namespace std;

 const int inf=;

 int n,m,Q,tot;

 int ddl[],dis[],head[];

 bool vis[];

 struct node{

     int next,to,val;

 }edge[];

 void add(int x,int y,int z)

 {

     edge[++tot].to=y;

     edge[tot].val=z;

     edge[tot].next=head[x];

     head[x]=tot;

 }

 int spfa_ask(int s,int t,int T)

 {

     memset(vis,,sizeof(vis));

     for(int i=;i<n;i++) dis[i]=inf;

     queue<int>q;

     q.push(s);dis[s]=;vis[s]=;

     while(!q.empty())

     {

         int x=q.front();

         q.pop();vis[x]=;

         for(int i=head[x];i!=-;i=edge[i].next)

         {

             int y=edge[i].to;

             if(dis[y]>dis[x]+edge[i].val&&ddl[y]<=T&&ddl[x]<=T)

             {

                 dis[y]=dis[x]+edge[i].val;

                 if(!vis[y]) q.push(y),vis[y]=;

             }

         }

     }

     if(dis[t]==inf) dis[t]=-;

     return dis[t];

 }

 int main()

 {

     memset(head,-,sizeof(head));

     scanf("%d%d",&n,&m);

     for(int i=;i<n;i++) scanf("%d",&ddl[i]);

     for(int i=;i<=m;i++)

     {

         int x=,y=,z=;

         scanf("%d%d%d",&x,&y,&z);

         add(x,y,z);add(y,x,z);

     }

     scanf("%d",&Q);

     while(Q--)

     {

         int x=,y=,T=;

         scanf("%d%d%d",&x,&y,&T);

         printf("%d\n",spfa_ask(x,y,T));

     }

     return ;

 }

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

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

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

正解：

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

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

Code

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int n,m,Q,pos,limit;

 int ddl[];

 int f[][];

 int main()

 {

     scanf("%d%d",&n,&m);

     memset(f,0x3f,sizeof(f));

     limit=f[][];

     for(int i=;i<n;i++) scanf("%d",&ddl[i]),f[i][i]=;

     for(int i=;i<=m;i++)

     {

         int x=,y=,z=;

         scanf("%d%d%d",&x,&y,&z);

         f[x][y]=z;f[y][x]=z;

     }

     scanf("%d",&Q);

     while(Q--)

     {

         int x=,y=,t=;

         scanf("%d%d%d",&x,&y,&t);

         if(ddl[x]>t||ddl[y]>t)

         {

             printf("-1\n");

             continue;

         }

         while(ddl[pos]<=t&&pos<n)

         {

             for(int i=;i<n;i++)

                 for(int j=;j<n;j++)

                     f[i][j]=min(f[i][j],f[i][pos]+f[pos][j]);

             pos++;

         }

         if(f[x][y]==limit)

         {

             printf("-1\n");

             continue;

         }

         printf("%d\n",f[x][y]);

     }

     return ;

 }

审题！审题！别丢条件！

巴特西

Luogu P1119 灾后重建【floyd】By cellur925

最新文章

热门文章

巴特西

Luogu P1119 灾后重建 【floyd】By cellur925

最新文章

热门文章

Luogu P1119 灾后重建【floyd】By cellur925