分层最短路与最短路dp

方法一：分层最短路

1.首先我们对这个函数进行分析，发现他是一个周期为3的周期函数，也就是说经过三次迭代就会回到之前的数

2.怎么说呢，现在就是有一种怪怪的感觉，代码什么地都能看懂，也都能敲的出来，但是感觉还是没有深刻的理解题目的意思，我去看题解都是说分三层，然后跑一遍dijkstra就行，我觉得分层最短路就是把所有的情况都列出来，然后在这个三层图上进行一次求最短路的过程，与平常不同的是平常的图已经给我们了。而分层图需要我们自己建立，这也是分层图可以用dp思想的原因之一吧，因为有时候我们不能把所有的情况都列出来，所以就在选与不选之间取一个最优值，因为最后到达目的地的时候有三种情况，也就是图中三次迭代的情况，所以我们最后只需要在遍历一次三种结果取最小就行，感觉目前的我就只知道知其然不知其所以然，刚刚开始接触分层最短路，或许哪天我明白了它的精髓那一定会回来写下的感想，与大家一起分享，共同进步~

这份代码需要注意就是与w相关的变量一定要用double类型去定义

#include <bits/stdc++.h>
using namespace std;
typedef pair<double, int> q;
const int maxn = 1e6 + 10;
const  double inf = 0x3f3f3f3f;

int head[maxn], n, m, tot, vis[maxn];
double dis[maxn];
struct node
{
   int to, next;
   double w;
} e[maxn * 5];

void add(int u, int v, double w)
{
   e[++tot].to = v;
   e[tot].w = w;
   e[tot].next = head[u];
   head[u] = tot;
}

void dijkstra()
{
   priority_queue<q> qp;
   for (int i = 1; i <= 3 * n; ++i)
      dis[i] = inf;
   dis[1] = 0;
   qp.push(make_pair(0, 1));
   while (!qp.empty())
   {
      q cur = qp.top();
      qp.pop();
      int u = cur.second;
      if (vis[u])
         continue;
      vis[u] = 1;
      for (int i = head[u]; ~i; i = e[i].next)
      {
         int v = e[i].to;
         if (dis[v] > dis[u] + e[i].w)
         {
            dis[v] = dis[u] + e[i].w;
            qp.push(make_pair(-dis[v], v));
         }
      }
   }
}
int main()
{
   memset(head, -1, sizeof(head));
   scanf("%d%d", &n, &m);
   for (int i = 1; i <= m; ++i)
   {
      int u, v;
      double w;
      scanf("%d%d%lf", &u, &v, &w);
      add(u, v + n, fabs(w));
      add(v, u + n, fabs(w));
      w = (1.0 / (1 - w));
      add(u + n, v + 2 * n, fabs(w));
      add(v + n, u + 2 * n, fabs(w));
      w = (1.0 / (1 - w));
      add(u + 2 * n, v, fabs(w));
      add(v + 2 * n, u, fabs(w));
   }
   dijkstra();
   double ans = inf;
   for (int i = 0; i <= 2; ++i)
      ans = min(ans, dis[n + i * n]);
   if (ans == inf)
      printf("-1\n");
   else
      printf("%.3lf\n", ans);
}

方法二：最短路dp

题目分析
刚开始见这个题目的时候我是很懵逼的，完全不知道如何下手，想了很久很久，逐渐的有点思路了…

首先我们应该对这个函数十分的敏感，因为这就是高中数学经典的一个周期函数，经过迭代我们发现他是一个以周期为3的周期函数，经过三次之后又回到了之前的值

其次，dp指的是一种思想，在选与不选之间，取一个最优值，我们在遍历最短路的时候，只要走过一条边那么其余所有的边都会发生改变，那么我们就用dijkstra跑出所有的情况，因为最后那个点只有三种情况，我们只需要最后在三种情况中选出最小的那个，如果最小的那个存在路径那么就是我们所需要的答案

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
const int inf = 0x3f3f3f3f;
double getdis(int x, int t) //分三种情况取值
{
   if (t == 0)
      return abs(1.0 * x);
   else if (t == 1)
      return abs(1.0 / (1.0 - x));
   else
      return abs(1.0 - 1.0 / x);
}

struct node1
{
   int to, w, next;
} e[maxn];

int n, m, tot;
int head[maxn];
void add(int u, int v, int w) //链式前向星加班
{
   e[++tot].to = v;
   e[tot].w = w;
   e[tot].next = head[u];
   head[u] = tot;
}
double dis[maxn][5];
struct node
{
   int id, t;
   double dis;
   bool operator<(const node x) const
   {
      return dis > x.dis;
   }
};
priority_queue<node> q;
bool vis[maxn][5];
void dijkstra()
{
   for (int i = 1; i <= n; ++i)
      dis[i][0] = dis[i][1] = dis[i][2] = inf;
   dis[1][0] = 0;
   node t;
   t.id = 1;
   t.t = 0;
   t.dis = dis[1][0];
   q.push(t);
   while (!q.empty())
   {
      int u = q.top().id;
      int t = q.top().t;
      q.pop();
      if (vis[u][t]) //如果改点已经被访问了，那么就跳过改点
         continue;
      vis[u][t] = 1;
      for (int i = head[u]; ~i; i = e[i].next) //如果没有，那么依次遍历改点的邻接点
      {
         int v = e[i].to;
         int t2 = (t + 1) % 3; //因为t的初始值是0,1,2.所以这里要加一再模3
         double v2 = getdis(e[i].w, t);
         if (vis[v][t2])
            continue;
         if (dis[v][t2] > dis[u][t] + v2) //对边进行松弛操作
         {
            dis[v][t2] = dis[u][t] + v2;
            node ne;
            ne.id = v;
            ne.t = t2;
            ne.dis = dis[v][t2];
            q.push(ne);
         }
      }
   }
}
int main()
{
   memset(head, -1, sizeof(head));
   scanf("%d%d", &n, &m);
   for (int i = 1; i <= m; ++i)
   {
      int a, b, c;
      scanf("%d%d%d", &a, &b, &c);
      add(a, b, c);
      add(b, a, c);
   }
   dijkstra();
   double ans = inf;
   for (int i = 0; i <= 2; ++i) //最后再选一条最短的就行
      ans = min(ans, dis[n][i]);
   if (ans == inf)
      puts("-1");
   else
      printf("%.3lf\n", ans);
}