杭电5636 Shortest Path （Floyd最短路）

痛定思痛。 2022-07-27 14:42 129阅读 0赞

题目链接：  
[http://acm.hdu.edu.cn/showproblem.php?pid=5636][http_acm.hdu.edu.cn_showproblem.php_pid_5636]

题目大意：  
有一条长度为n的链. 节点i和i+1之间有长度为1的边. 现在又新加了3条边, 每条边长度都是1. 给出m个询问, 每次询问两点之间的最短路.

解题思路：  
将需要用的点的编号提取出来，最多8个（因为询问的点和和新增加边的点可能重复），然后将连边的点距离变为1，未连边的点就和下一个点连边，距离为编号之差，连完边后用floyd跑一遍，即可知道距离。

#include <vector>
    #include <list>
    #include <map>
    #include <set>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <bitset>
    #include <algorithm>
    #include <functional>
    #include <numeric>
    #include <utility>
    #include <sstream>
    #include <iostream>
    #include <iomanip>
    #include <cstdio>
    #include <cmath>
    #include <cstdlib>
    #include <cstring>
    #include <ctime>
    #include <cassert>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define Cl0(a) memset((a),0,sizeof(a))
    using namespace std;
    const int inf=1e9+7;
    const int inf1=-1*1e9;
    typedef long long LL;
    int a[10];
    long long int ans[100005];
    int main()
    {
        int t;
        RI(t);
        while(t--)
        {
            int n,m,s,t;
            RII(n,m);
            int a1,b1,a2,b2,a3,b3;
            RII(a1,b1);
            RII(a2,b2);
            RII(a3,b3);
            a[8]=-1;
            for(int sa=1; sa<=m; sa++)
            {
                RII(s,t);
                a[0]=a1;
                a[1]=b1;
                a[2]=a2;
                a[3]=b2;
                a[4]=a3;
                a[5]=b3;
                a[6]=s;
                a[7]=t;
                sort(a,a+8);
                int b[10],len=0,dp[8][8];
                for(int i=0; i<8; i++)
                    for(int j=0; j<8; j++)
                    {
                        if(i==j)  dp[i][j]=0;
                        else dp[i][j]=inf;
                    }
                for(int i=0; i<8; i++)
                {
                    if(a[i]!=a[i+1])
                    {
                        b[len++]=a[i];
                    }
                }
    
                for(int i=0; i<len-1; i++)
                {
                    dp[i][i+1]=b[i+1]-b[i];
                    dp[i+1][i]=b[i+1]-b[i];
                }
                int x=lower_bound(b,b+len,a1)-b;
                int y=lower_bound(b,b+len,b1)-b;
                dp[x][y]=1;
                dp[y][x]=1;
                x=lower_bound(b,b+len,a2)-b;
                y=lower_bound(b,b+len,b2)-b;
                dp[x][y]=1;
                dp[y][x]=1;
                x=lower_bound(b,b+len,a3)-b;
                y=lower_bound(b,b+len,b3)-b;
                dp[x][y]=1;
                dp[y][x]=1;
                x=lower_bound(b,b+len,s)-b;
                y=lower_bound(b,b+len,t)-b;
                for(int k=0; k<len; k++)
                    for(int i=0; i<len; i++)
                        for(int j=0; j<len; j++)
                        {
                            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
                        }
    
                ans[sa]=dp[x][y];
            }
            long long int ans1=0;
            for(int i=1; i<=m; i++)
            {
                ans1=(ans1+ans[i]*i)%inf;
            }
            printf("%lld\n",ans1);
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_5636]: http://acm.hdu.edu.cn/showproblem.php?pid=5636