本文主要是介绍URAL 1934 Black Spot --- 简单最短路变形，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
边权为1，在维护最短路的同时维护p值最小，我直接存的(1-p)，即不遇见的概率，要使得这个值最大。
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define eps 1e-6
#define ll long long
const int maxn=100010;
const int maxm=100010;
using namespace std;struct node
{int v,w,next;double p;
}e[maxm<<1];
int vis[maxn],h,head[maxn],n,m,d[maxn],pre[maxn];
double p[maxn];void addedge(int a,int b,double c)
{e[h].v=b;e[h].w=1;e[h].p=c;e[h].next=head[a];head[a]=h++;
}void spfa(int s)
{int x,v,i;for(i=0;i<=n;i++)p[i]=0,d[i]=inf;memset(vis,0,sizeof vis);memset(pre,-1,sizeof pre);p[s]=1,vis[s]=1,d[s]=0;queue<int> q;q.push(s);while(!q.empty()){x=q.front();q.pop();vis[x]=0;for(i=head[x];i!=-1;i=e[i].next){v=e[i].v;if(d[v]>d[x]+1){d[v]=d[x]+1;p[v]=p[x]*e[i].p;pre[v]=x;if(!vis[v]){vis[v]=1;q.push(v);}}else if(d[v]==d[x]+1){if(p[v]<p[x]*e[i].p){p[v]=p[x]*e[i].p;pre[v]=x;if(!vis[v]){vis[v]=1;q.push(v);}}}}}return ;
}
int flag;
void output(int x)
{if(pre[x]!=-1)output(pre[x]);if(flag) flag=0;else putchar(' ');printf("%d",x);
}int main()
{int a,b,s,t;double c;while(~scanf("%d%d",&n,&m)){h=0;memset(head,-1,sizeof head);scanf("%d%d",&s,&t);while(m--){scanf("%d%d%lf",&a,&b,&c);addedge(a,b,1-c/100);addedge(b,a,1-c/100);}spfa(s);printf("%d %.8lf\n",d[t]+1,1-p[t]);flag=1;output(t);puts("");}return 0;
}
这篇关于URAL 1934 Black Spot --- 简单最短路变形的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
