牛客 Rinne Loves Dynamic Graph （最短路dp与分层最短路）

题目描述
Rinne 学到了一个新的奇妙的东西叫做动态图，这里的动态图的定义是边权可以随着操作而变动的图。
当我们在这个图上经过一条边的时候，这个图上所有边的边权都会发生变动。
定义变动函数
，表示我们在图上走过一条边后，图的边权变动情况。
这里指的“图的变动”的意思是将每条边的边权代入上函数，得到的值即为该次变动后的边权。
现在 Rinne 想要知道，在这个变动的图上从 1 到 n 的最短路径。
因为 Rinne 不喜欢负数，所以她只需要你输出经过的边权权值绝对值之和最小的那个值就可以了。
输出答案保留三位小数。
输入描述:
第一行两个正整数 N,M，表示这个动态图的点数和边数。
接下来 M 行，每行三个正整数 u,v,w，表示存在一条连接点 u,v 的无向边，且初始权值为 w。
输出描述:
如果能到达的话，输出边权绝对值之和最小的答案，保留三位小数。
否则请输出 -1。

输入
3 3
1 2 2
2 3 2
3 1 3

输出
3.000
说明

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

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

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

最短路dp代码

#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);
}

​

分层最短路

怎么说呢，现在就是有一种怪怪的感觉，代码什么地都能看懂，也都能敲的出来，但是感觉还是没有深刻的理解题目的意思，我去看题解都是说分三层，然后跑一遍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);
}

自我增值12法 ———— 1）每天读书；2）学习新的语言；3）战胜你的恐惧；4）提升你的技能；5）时常检讨自己；6）向你佩服的人学习；7）多做有意义的事；8）培养一个新的爱好；9）有规律作息；10）帮助他人；11）让过去的过去；12）从现在开始。 ​​​