链接：https://ac.nowcoder.com/acm/contest/26077/1032
来源：牛客网
题目描述
Rinne 学到了一个新的奇妙的东西叫做动态图，这里的动态图的定义是边权可以随着操作而变动的图。当我们在这个图上经过一条边的时候，这个图上所有边的边权都会发生变动。
定义变动函数 f(x)=11−xf(x) = \frac{1}{1-x}f(x)=1−x1，表示我们在图上走过一条边后，图的边权变动情况。 这里指的“图的变动”的意思是将每条边的边权代入上函数，得到的值即为该次变动后的边权。 现在 Rinne 想要知道，在这个变动的图上从 1 到 n 的最短路径。
因为 Rinne 不喜欢负数，所以她只需要你输出经过的边权权值绝对值之和最小的那个值就可以了。
输出答案保留三位小数。
输入描述:
第一行两个正整数 N,M，表示这个动态图的点数和边数。
接下来 M 行，每行三个正整数 u,v,w，表示存在一条连接点 u,v 的无向边，且初始权值为 w。
输出描述:
如果能到达的话，输出边权绝对值之和最小的答案，保留三位小数。示例1
否则请输出 -1。
输入
复制3 3 1 2 2 2 3 2 3 1 3
输出
复制3.000
说明
走 1→2→31 \to 2 \to 31→2→3，总花费 2+∣11−2∣=32 + |\frac{1}{1-2}| = 32+∣1−21∣=3
备注:
n≤100000,m≤300000,2≤x≤1000n \leq 100000,m \leq 300000,2 \leq x \leq 1000n≤100000,m≤300000,2≤x≤1000
分析
由于 x = 1 / 1 - x
x' = 1 / (1 - 1 / (1 - x))
x'' = 1 / 1 - x' = x
所以三者构成三个循环层，
将第一层指向第二层，第二层指向第三层，第三层指向第一层
再跑一边dijkstra，然后枚举最小值就可以了。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e5 + 5;
typedef pair<int,double> PID;
typedef pair<double,int> PDI;
const double INF = 99999999999;
int n,m;
//vector<PID > vv[3*MAX];
double dis[MAX*3];
bool vis[MAX*3];
int head[MAX*3];
struct Node {
int to,ne;
double w;
} e[MAX*15];
int tot;
void add(int u,int v,double w) {
e[++tot].to = v;
e[tot].w = w;
e[tot].ne = head[u];
head[u] = tot;
}
void Dijkstra() {
for(int i = 1; i<=3*n; i++) dis[i] = INF;
dis[1] = 0;
priority_queue<PDI> pq;
pq.push(pm(0,1));
while(!pq.empty()) {
PDI cur = pq.top();pq.pop();
if(vis[cur.se]) continue;
vis[cur.se] = 1;
for(int i = head[cur.se]; i!=-1; i=e[i].ne) {
int v = e[i].to;
if(dis[cur.se] + e[i].w < dis[v]) {
dis[v] = dis[cur.se] + e[i].w;
pq.push(pm(-dis[v],v));
}
}
}
}
int main()
{
memset(head,-1,sizeof head);
cin>>n>>m;
int u,v;
double w;
for(int i = 1; i<=m; i++) {
scanf("%d%d%lf",&u,&v,&w);
//w = fabs(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 > 9999999999) printf("-1\n");
else printf("%.3lf\n",ans);
return 0 ;
}
标签：pq,Rinne,int,Graph,边权,Dynamic,MAX,include,dis From： https://www.cnblogs.com/er007/p/16617518.html