杭電5636 Shortest Path （Floyd最短路）

題目連結：

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=+;
const int inf1=-*;
typedef long long LL;
int a[];
long long int ans[];
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[]=-;
        for(int sa=; sa<=m; sa++)
        {
            RII(s,t);
            a[]=a1;
            a[]=b1;
            a[]=a2;
            a[]=b2;
            a[]=a3;
            a[]=b3;
            a[]=s;
            a[]=t;
            sort(a,a+);
            int b[],len=,dp[][];
            for(int i=; i<; i++)
                for(int j=; j<; j++)
                {
                    if(i==j)  dp[i][j]=;
                    else dp[i][j]=inf;
                }
            for(int i=; i<; i++)
            {
                if(a[i]!=a[i+])
                {
                    b[len++]=a[i];
                }
            }

            for(int i=; i<len-; i++)
            {
                dp[i][i+]=b[i+]-b[i];
                dp[i+][i]=b[i+]-b[i];
            }
            int x=lower_bound(b,b+len,a1)-b;
            int y=lower_bound(b,b+len,b1)-b;
            dp[x][y]=;
            dp[y][x]=;
            x=lower_bound(b,b+len,a2)-b;
            y=lower_bound(b,b+len,b2)-b;
            dp[x][y]=;
            dp[y][x]=;
            x=lower_bound(b,b+len,a3)-b;
            y=lower_bound(b,b+len,b3)-b;
            dp[x][y]=;
            dp[y][x]=;
            x=lower_bound(b,b+len,s)-b;
            y=lower_bound(b,b+len,t)-b;
            for(int k=; k<len; k++)
                for(int i=; i<len; i++)
                    for(int j=; 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=;
        for(int i=; i<=m; i++)
        {
            ans1=(ans1+ans[i]*i)%inf;
        }
        printf("%lld\n",ans1);
    }
    return ;
}