拆点____ 行车路线

3255. 行车路线

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

小芳将可能的道路分为大道和小道。

大道比较好走，每走 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 号路口是连通的。

输出格式

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

数据范围

对于 30% 的评测用例，1≤n≤8，1≤m≤10；
对于另外 20% 的评测用例，不存在小道；
对于另外 20% 的评测用例，所有的小道不相交；
对于所有评测用例，1≤n≤500，1≤m≤10^5，1≤a,b≤n，t 是 0 或 1，c≤10^5。
保证答案不超过 10^6。

输入样例：

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

样例解释

从 1 走小道到 2，再走小道到 3，疲劳度为 5^2=25；然后从 3 走大道经过 4 到达 5，疲劳度为 20+30=50；最后从 5 走小道到 6，疲劳度为 1。

总共为 76。

因为保证答案不超过10^6, 所以连续小路长度超过1000
因为点的数据范围为500，所以可以拆点，第二维表示当前连续小路长度 

#include 
 
using namespace std;
 
const int N = 510, M = 200010, INF = 1e6;
 
int n, m;
int h[N], e[M], f[M], w[M], ne[M], idx;  //f表示道路类型
int dist[N][1010];
bool st[N][1010];
 
struct Node
{
    int x, y, v;  //x当前点，y当前连续小路长度，v为dist[x][y]
    bool operator< (const Node& t) const
    {
        return v > t.v;  //小根堆（从小到大）
    }
};
 
void add(int t, int a, int b, int c)
{
    e[idx] = b, f[idx] = t, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
 
void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1][0] = 0;
    priority_queue heap;
    heap.push({1, 0, 0});
    
    while (heap.size())
    {
        Node t = heap.top();
        heap.pop();
        
        if (st[t.x][t.y]) continue;  //dijkstra()所有点只遍历一次
        st[t.x][t.y] = true;
        
        for (int i = h[t.x]; ~i; i = ne[i])
        {
            int j = e[i], y = t.y;
            if (f[i])  //小路
            {
                y += w[i];  //小路长度更新
                if (y <= 1000)  //连续小路长度一定小于1000
                {
                    if (dist[j][y] > t.v - t.y * t.y + y * y)
                    {
                        dist[j][y] = t.v - t.y * t.y + y * y;
                        if (dist[j][y] <= INF)
                            heap.push({j, y, dist[j][y]});
                    }
                }
            }
            else
            {
                if (dist[j][0] > t.v + w[i])
                {
                    dist[j][0] = t.v + w[i];
                    if (dist[j][0] <= INF)
                        heap.push({j, 0, dist[j][0]});
                }
            }
        }
    }
}
 
int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while (m --)
    {
        int t, a, b, c;
        scanf("%d%d%d%d", &t, &a, &b, &c);
        add(t, a, b, c), add(t, b, a, c);
    }
    
    dijkstra();
    
    int res = INF;
    for (int i = 0; i <= 1000; i ++) res = min(res, dist[n][i]);
    //表示最后一段小路的长度为i的前提下，1到n的最短距离
    
    cout << res;
    
    return 0;
}