Dijkstra + 链式前向星存图全WA求助
  • 板块P1576 最小花费
  • 楼主3a51_
  • 当前回复8
  • 已保存回复8
  • 发布时间2022/3/1 21:24
  • 上次更新2023/10/28 07:28:00
查看原帖
Dijkstra + 链式前向星存图全WA求助
327444
3a51_楼主2022/3/1 21:24
/*
work by:Tothetime_tolife
time:1s
space:128MB
*/
#include<bits/stdc++.h>
#define int long long
#define Tothetime_tolife using
#define AK namespace
#define IOI std
Tothetime_tolife AK IOI;
const int Mod1=998244353;
const int Mod2=1000000007;
int gcd(int a,int b){return __gcd(a,b);}
int lcm(int a,int b){return a*b/gcd(a,b);}
int qpow(int a,int b){int res=1;while(b){if(b&1){res=res*a%Mod1;}b>>=1;a=a*a%Mod1;}return res%Mod1;}
template <typename T> inline void read(T& x) {
	x=0;T f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=x*f;
	return;
}
template <typename T,typename ...Arg>void read(T& x,Arg& ...arg){
	read(x);
	read(arg...);
}
template <typename T>void write(T x) {
	if(x<0)putchar('-'),x=-x;
	if(x<10)putchar(x+'0');
	else write(x/10),putchar(x%10+'0');
}
template <typename T,typename ...Arg>void write(T& x,Arg& ...arg){
	write(x);
	putchar(' ');
	write(arg...);
}
const int N=2005;
const int M=100005;
const int Max=2147483647;
int n,m,l,S,T,ans,dis[N],head[N],cnt,x,y,z,t,Cnt=1;
int to[2*M],nxt[2*M],val[2*M],X[2*M],Y[2*M],Z[2*M];
bool vis[N];
struct Node{
	int id,w;
	friend bool operator<(const Node A,const Node B){
		return A.w>B.w;
	}
};
inline void add(int u,int v,int w){
	to[++cnt]=v;
	nxt[cnt]=head[u];
	head[u]=cnt;
	val[cnt]=w;
	return;
}
priority_queue<Node> Q;
void dij(){
	for(int i=1;i<=n;i++) dis[i]=Max;
	Node now;
	now.id=S;now.w=0;
	dis[S]=0;
	int p,ww;
	Q.push(now);
	while(!Q.empty()){
		Node x=Q.top();
		Q.pop();
		p=x.id;
		ww=x.w;
		if(vis[p] || dis[p]!=ww){
			continue;
		}
		vis[p]=1;
		int u;
		for(register int i=head[p];i;i=nxt[i]){
			u=to[i];
			if(dis[p]/double(1-(double(val[i])/100.0))<dis[u]){
				dis[u]=dis[p]/double(1-(double(val[i])/100.0));
				now.id=u;now.w=dis[u];
				Q.push(now);
			}
		}
	}
	return;
}
signed main()
{
	//;;;;;
	read(n,m);
	for(int i=1;i<=m;i++){
		read(x,y,z);
		add(x,y,z);
		add(y,x,z);
	}
	read(S,T);
	dij();
	printf("%.8f",100.0/double(dis[T]));
	return 0;
}
//QwQ
2022/3/1 21:24
加载中...