Rinne 學到了一個新的奇妙的東西叫做動態圖，這里的動態圖的定義是邊權可以隨著操作而變動的圖，
當我們在這個圖上經過一條邊的時候，這個圖上所有邊的邊權都會發生變動，
定義變動函式 f(x)=1/(1-x)，表示我們在圖上走過一條邊后，圖的邊權變動情況，
這里指的“圖的變動”的意思是將每條邊的邊權代入上函式，得到的值即為該次變動后的邊權，
現在 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
說明
#include<bits/stdc++.h>
using namespace std;
class ty
{
public:
ty(int to,double length,int next):to(to),length(length),next(next){};
int to;
double length;
int next;
int times=0;
bool operator <(const ty&t) const
{
return this->length>t.length;
}
};
int head[100000+5];
double dis[100000+5][3];
vector<ty> edge;
void insertEdge(int x,int y,double length)
{
edge.emplace_back(y,length,head[x]);
head[x]=edge.size()-1;
}
double calculate(int times,double length)
{
if(times==0) return length;
else if(times==1) return 1/(length-1);
else return 1-1/length;
}
void dijkstra(int start,int end)
{
priority_queue<ty> pq;
memset(dis,0x7f,sizeof(dis));
pq.emplace(start,0,-1);
dis[start][0]=0;
while(!pq.empty())
{
int now=pq.top().to, timesNow=pq.top().times;
pq.pop();
if(now==end)
{
cout<<fixed<<setprecision(3)<<dis[end][timesNow];
return ;
}
for(int i=head[now];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(dis[v][(timesNow+1)%3]>dis[now][timesNow]+calculate(timesNow,edge[i].length))
{
dis[v][(timesNow+1)%3]=dis[now][timesNow]+calculate(timesNow,edge[i].length);
ty t=ty(v,dis[v][(timesNow+1)%3],-1);
t.times=(timesNow+1)%3;
pq.push(t);
}
}
}
cout<<-1;
return;
}
int main()
{
int n,m;
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
memset(head,-1,sizeof(head));
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
insertEdge(a,b,c);
insertEdge(b,a,c);
}
dijkstra(1,n);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/265950.html
標籤：其他
上一篇：Coordinatorlayout嵌套滑動，自定義Behavior，聽我來講講？
下一篇：Android Studio錯誤代碼解決：The emuilator process for AVD Nexus_ 5X_ API_ 30_ x86 was killed.