涉及知识点：
solution
- 我们发现当我们走过一条边后，所有的点的边权都会发生变化
- 但是当我们走过三次后他就会变回原来的值，即循环周期为3
- 想成一般的对短路就好了
- 即我们相成一个三层的最短路
- 每次转移都是从上一层转移过来的
- 这个地方用堆优化的迪杰斯特拉就好了
std:
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
double fun(double x)
{
return 1.0 / (1.0 - x);
}
typedef pair<int,int> PII;
typedef pair<double,pair<int,int>> PDII;
const int N = 1e5 + 10;
vector<PII>v[N];
int n,m;
double dist[N][3];
bool st[N][3];
void dijkstra()
{
priority_queue<PDII,vector<PDII>,greater<PDII>>q;
q.push({0,{1,0}});
for(int i = 1;i <= n;i ++)
{
for(int j = 0;j < 3;j ++)
{
dist[i][j] = 1e9;
}
}
dist[1][0] = 0;
while(q.size())
{
auto t = q.top();q.pop();
int u = t.second.first,step = t.second.second;
if(st[u][step]) continue;
st[u][step] = true;
for(auto &x : v[u])
{
double dis = x.second;
int ver = x.first;
if(step == 1) dis = fun(dis);
else if(step == 2)
{
dis = fun(dis);
dis = fun(dis);
}
dis = abs(dis);
int tt = (step + 1) % 3;
if(dist[ver][tt] > dist[u][step] + dis){
dist[ver][tt] = dist[u][step] + dis;
q.push({dist[ver][tt],{ver,tt}});
}
}
}
}
int main()
{
cin >> n >> m;
for(int i = 0;i < m;i ++)
{
int a,b,c;
cin >> a >> b >> c;
v[a].push_back({b,c});
v[b].push_back({a,c});
}
dijkstra();
double m = 1e9;
if(m > dist[n][0]) m = dist[n][0];
if(m > dist[n][1]) m = dist[n][1];
if(m > dist[n][2]) m = dist[n][2];
if(m == 1e9) cout << -1 << endl;
else
{
printf("%.3lf",m);
}
return 0;
}