Bellman-Ford算法，dijstra算法，循环dp问题

这题很好，让我重新认识到了最短路到底是为解决了一个什么样的问题！！！！

题意：

图片说明

分析：

首先，我不会分层图！！！！
所以，这题我主要是围绕dp展开。
我们必须要知道题中所给函数1/(1-x)是个周期为三的周期函数
那么边权就为x,1/(x-1),(x-1)/x 这里是取过绝对值的
这是前提，没有意识到这一点无从展开的。

这里我给一个dp状态
dp[i][j]:点i在j状态时到达状态为0的节点1 的最短路径
j状态共有三种对应上面周期函数的每一种变化[x,1/(x-1),(x-1)/x]

那我们所求的答案就是min(dp[n][0],dp[n][1],dp[n][2])
理解？

状态转移方程为：
dp[i][j] = min(d[k][(j-1)%3] + e[i][k].cost[(j-1)%3]，k为j的相邻点 (j+1)%3为前一个状态)
是否？这应该就是我们的状态转移方程。且我们知道初始状态d[1][0] = 0

但是啊，我们发现如果我们按照这个方程去转移递归的话，我们会陷入死循环！！
仔细想想，我们会在两个相邻节点之间来回递归永远出不去。准确说，我们会在环间来回递归，永远出不去！

这是很惨的！循环dp！！！！

正当我一筹莫展的时候，我翻开了Bellman-Ford算法，恍然大悟！！！
请看：
图片说明

我们发现，Bellman-Ford实际上也是总结出了一个循环dp ：
d[i] = min(d[j]+(从j到i的cost)|e=(j,i)属于E)

在下面的说明中也说了，如果图中有环则无法计算，会像我们一样无限递归。
这是不是和我们的dp所面临的问题一样？
而他是如何解决这个问题的呢？
松弛操作！！！！！
Bellman-Ford通过松弛操作解决了dp循环问题。而松弛操作的前提是没有负循环，我们当然没有负循环，我们连负边都没有！！
所以我们可以实行Bellman的松弛操作！
众所周知，Dijstra算法和SPFA算法不过是Bellman-Ford算法的技术优化，其原理和操作未变。
SPFA算法没有额外条件还是只要没有负环就可以了。Dijstra算法则是还需要没有负边，我们没有负边
所以我们这里选择最优的Dijstra算对Bellman-Ford算法进行优化。

如果写不出的话，建议仔细看看Bellman-Ford算法怎么写的，用Bellman-Ford算法写了本题后，再用Dijstra算法优化。

代码如下：

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>
#include<iomanip>
using namespace std;
typedef pair<int, int> pii;
typedef pair<double, pii> pdi;
struct edge { int to;vector<double> cost; };
const int max_n = 1e5 + 100;
const double inf = 1e18;
vector<edge> G[max_n];
int n, m;
double d[max_n][3];

void dijstra(int s,int t) {
    for (int i = 1;i <= n;i++)
        for (int j = 0;j < 3;j++)
            d[i][j] = inf;
    d[s][t] = 0;
    priority_queue<pdi, vector<pdi>, greater<pdi>> que;
    que.push({ d[s][t],{s,t} });
    while (!que.empty()) {
        pdi p = que.top();que.pop();
        pii pos = p.second;
        if (d[pos.first][pos.second] < p.first)continue;
        for (int i = 0;i < G[pos.first].size();i++) {
            edge e = G[pos.first][i];
            if (d[e.to][(pos.second + 1) % 3] > d[pos.first][pos.second] + e.cost[pos.second]) {
                d[e.to][(pos.second + 1) % 3] = d[pos.first][pos.second] + e.cost[pos.second];
                que.push({ d[e.to][(pos.second + 1) % 3],{e.to,(pos.second + 1) % 3} });
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1;i <= m;i++) {
        int u, v;double w;cin >> u >> v >> w;
        edge e1;e1.to = u;e1.cost = { w,1 / (w - 1),(w - 1) / w };
        G[v].push_back(e1);
        edge e2;e2.to = v;e2.cost = { w,1 / (w - 1),(w - 1) / w };
        G[u].push_back(e2);
    }
    dijstra(1, 0);
    double ans = inf;
    for (int i = 0;i < 3;i++)ans = min(ans, d[n][i]);
    if (ans == inf)cout << -1 << endl;
    else cout << fixed << setprecision(3) << ans << endl;
}

关键在于对松弛操作的理解，他到底解决了什么问题？ 无负循环的循环dp问题！！！！！！

Rinne Loves Dynamic Graph

Bellman-Ford算法，dijstra算法，循环dp问题

题意：

分析：

代码如下：