题解 | #Rinne Loves Dynamic Graph#

思路

求从 1 到 n 的最短路，需注意的是 图上所有边的边权会实时改变
如何改变：每次走过一条边之后，所有的 x 都会 执行一次操作：x = 1/(1-x)，x 是 边权，所有的 x 指所有边
即 边权会随着走过的边的数目的改变而改变

所以该题 不再仅仅是最短路问题，而是变成了 最短路 + dp 问题

不妨令 dist[i][j]：表示 从 1 到 i 经过了 j 条边的最短路
所以 我们最终只需求 min（ dist[n][0]，dist[n][1]，dist[n][2]，...... ，dist[n][M] ） M 代表最多走过的边的数目

但是 因为边是双向边，所以理论上来讲 我们可走过无穷条边 ，开数组的话 需开成 dist[点的数目][正无穷]
显然 开不到那么大

所以我们需要作进一步的 优化：
观察 x = 1/(1-x) ，我们不难发现 执行三次该操作之后，x 会变回最初的 x
所以我们可以把 走过的边的数目 视为 0 、1 、2
0：表示走过了 3x 条边 ，x>=0
1：表示走过了 3x + 1条边，x>=0
2：表示走过了 3x + 2条边，x>=0

现在 dist[点的数目] [正无穷] 变成了 dist[点的数目] [3]

最终只需求 min( dist[n][0], dist[n][1], dist[n][2] ) 便可

注意：因为边权随着 走过边的数目的改变 而改变，所以我们需额外让 cnt 也入队

一些变量的解释:
cnt：走过边的数目 ，cnt取值 0、1、2
dist[i][j]：表示 从 1 到 i 经过了 '' j 条边 '' 的最短路 ，j 取值 0、1、2
st[i][j] = true 表示 从 1 到 i 经过了 '' j 条边 '' 的最短路已经确定 ，j 取值 0、1、2

综上，Code 如下 .

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 100010,M = 600010;

struct node{
    double distance;
    int id,cnt ;
    bool operator < (const node &x) const{
        return distance > x.distance;
    }
};
int n,m;
bool st[N][4];
double w[M],dist[N][4];
int h[N],e[M],ne[M],idx;

double change_w(double x,int t){
    t=t%3;
    while(t--){
       x = 1.0/(double)(1-x) ; 
    }
    if(x<0) x=-x;
    return x;
}

void add(int a,int b,double c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

double dijkstra(){
    for(int i=1;i<=n;i++) dist[i][0]=dist[i][1]=dist[i][2]=1e10;  // double型 不能用memset
    dist[1][0]=0; 
    priority_queue<node> heap;
    heap.push({0,1,0}) ;

    while(heap.size()){
        auto p=heap.top();
        heap.pop();
        int id=p.id,cnt=p.cnt;
        double distance=p.distance;

        if(st[id][cnt]) continue;

        st[id][cnt]=true;
        for(int i=h[id];i!=-1;i=ne[i]){
            int j=e[i];
            double d=change_w(w[i],cnt);
            if(dist[j][(cnt+1)%3]>distance+d){
                dist[j][(cnt+1)%3]=distance+d;
                heap.push({dist[j][(cnt+1)%3],j,(cnt+1)%3}) ;
            }
         }
    }  

    double res = 1e10;
    for(int i=0;i<3;i++) res=min(res,dist[n][i]);

    return res==1e10?-1:res;
} 

int main(){
    scanf("%d %d",&n,&m);
    memset(h,-1,sizeof h);

    while(m--){
        int a,b,w;
        scanf("%d %d %d",&a,&b,&w);
        add(a,b,w),add(b,a,w);
    }

    double t=dijkstra();
    if(t==-1) puts("-1");
    else printf("%.3f\n",t);

    return 0;
}