CCF 201712-4 行车路线 （spfa）

问题描述

小明和小芳出去乡村玩，小明负责开车，小芳来导航。

小芳将可能的道路分为大道和小道。大道比较好走，每走 1 公里小明会增加 1 的疲劳度。小道不好走，如果连续走小道，小明的疲劳值会快速增加，连续走 s 公里小明会增加 s^2 的疲劳度。

例如：有 5 个路口，1 号路口到 2 号路口为小道，2 号路口到 3 号路口为小道，3 号路口到 4 号路口为大道，4 号路口到 5 号路口为小道，相邻路口之间的距离都是 2 公里。如果小明从 1 号路口到 5 号路口，则总疲劳值为 (2+2)^2+2+2^2=16+2+4=22 。

现在小芳拿到了地图，请帮助她规划一个开车的路线，使得按这个路线开车小明的疲劳度最小。

输入格式

输入的第一行包含两个整数 n, m，分别表示路口的数量和道路的数量。路口由 1 至 n 编号，小明需要开车从 1 号路口到 n 号路口。

接下来 m 行描述道路，每行包含四个整数 t, a, b, c，表示一条类型为 t，连接 a 与 b 两个路口，长度为 c 公里的双向道路。其中 t 为 0 表示大道，t 为 1 表示小道。保证 1 号路口和 n 号路口是连通的。

输出格式

输出一个整数，表示最优路线下小明的疲劳度。

样例输入

6 7
1 1 2 3
1 2 3 2
0 1 3 30
0 3 4 20
0 4 5 30
1 3 5 6
1 5 6 1

样例输出

76

思路

对于同一个点，假设最后一次从大道走过来和从小道走过来的花费是一样的，显然大道比较划算，因为它对下一次走小道的消耗没有贡献，从而可以保证最优解。

那么，我们把大道和小道分开计算。

首先通过 Floyd 算法合并一下所有的小道，然后再通过 spfa 寻找最优解。

每一次的迭代中我们只需要考虑当前状态的转移即可：[大道/小道 -> 大道]、[大道 -> 小道]

AC 代码

#include<bits/stdc++.h>
#define IO ios::sync_with_stdio(false);\
    cin.tie(0);\
    cout.tie(0);
#define inf 0x3f3f3f
using namespace std;
typedef long long LL;
const int maxn = 5e2+10;

int n,m;
LL G[maxn][maxn];
LL G2[maxn][maxn];
LL dist[maxn];
LL dist2[maxn];
bool vis[maxn];

void floyd()
{
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=i+1; j<=n; j++)
                G2[i][j] = min(G2[i][j],G2[i][k]+G2[k][j]);
}

void init()
{
    memset(dist,inf,sizeof(dist));
    memset(dist2,inf,sizeof(dist2));
    memset(vis,false,sizeof(vis));
    memset(G,inf,sizeof(G));
    memset(G2,inf,sizeof(G2));
}

void spfa(int st,int ed)
{
    queue<int> sk;
    dist[st] = dist2[st] = 0;
    vis[st] = true;
    sk.push(st);
    while(!sk.empty())
    {
        int u = sk.front();
        sk.pop();
        vis[u] = false;
        for(int i=1; i<=n; i++)
        {
            int xlen = min(dist[u],dist2[u]);
            bool flag = false;
            if(dist[i] > xlen + G[u][i])
            {
                dist[i] = xlen + G[u][i];
                flag = true;
            }
            if(G2[u][i]!=4557430888798830399LL)
            {
                if(dist2[i] > dist[u] + G2[u][i] * G2[u][i])
                {
                    dist2[i] = dist[u] + G2[u][i] * G2[u][i];
                    flag = true;
                }
            }
            if(flag && !vis[i])
            {
                vis[i] = true;
                sk.push(i);
            }
        }
    }
}

int main()
{
    IO;
    init();
    cin>>n>>m;
    for (int i = 0; i < m ; i++)
    {
        LL t,a,b,c;
        cin>>t>>a>>b>>c;
        if(t)
            G2[a][b] = G2[b][a] = min(G2[a][b],c);
        else
            G[a][b] = G[b][a] = min(G[a][b],c);
    }
    floyd();
    spfa(1,n);
    cout<<min(dist[n],dist2[n])<<endl;
    return 0;
}