首页 > 代码库 > ACDream - Chasing Girl

ACDream - Chasing Girl

2024-07-15 04:13:18   224人阅读

先上题目：

Chasing Girl

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)
SubmitStatus

Problem Description

       YYS 是SCAU_ACM里相当有名气的高富帅， 又因为他曾代表SCAU参加 World Final 而被各路亲朋好友仰慕。但YYS 又有另外一个嗜好，就是泡妞。在大学的时候，他经常去找各个女友玩耍， 但在路上却又整天遇到膜拜他的渣渣，这令他非常烦恼。于是， 他每次去找女友都希望尽量避开膜拜他的渣渣。
       YYS 把校园抽象成n个点， m条双向路组成的图。由多次经验他统计出在某条路上遇到渣渣的概率， 他现在要从A走到B， 由于他急于跟女友xxx， 所以想选择一条长度最短，在此基础上遇到渣渣概率最小的路径。YYS此时的心思只有女友， 他想你帮他算一下， 最短的路径长度和最小的概率是多少。

 

 

Input

第一行一个整数T，代表测试数据的组数。
对每组数据， 
第一行， 两个整数n, m
接下来m行，每行4个整数 u, v, w, p， 代表u,v之间有一条长度为w双向路，在这条路遇到渣渣的概率为p%
最后一行， 两个整数A, B

数据范围：
1 <= T <= 100
1 <= n <= 1000
1 <= m <= 10000
1 <= u, v, A, B <= n
1 <= w <= 100
0 <= p < 100

数据保证无重边、无自环，并且A、B之间至少有一条路径。

 

 

Output

对每组数据，输出最短的路径长度和最小的概率(保留6位小数)。 

 

Sample Input

24 41 2 1 502 3 2 501 4 5 204 3 3 302 44 41 2 1 502 3 2 501 4 4 204 3 3 302 4

Sample Output

5 0.6500005 0.600000

　　比较简单的最短路，求一次最短路，同时算一下一路上不会遇到那些人的概率，如果遇到将要修改的距离等于已经得到的最短距离的话，就根据概率来判断，如果概率变大了就更新为新的概率。
　　输出的时候概率用1减一次就得到结果了(1-反面的概率)。
　　这里的图是有环的，看自己的笔记好像是说DIJ只可以求DAG，所用用了SPFA，但是小伙伴说用DIJ也过了······

上代码：

 1 /* 2 * this code is made by sineatos 3 * Problem: 1180 4 * Verdict: Accepted 5 * Submission Date: 2014-07-31 15:23:49 6 * Time: 228MS 7 * Memory: 1884KB 8 */ 9 #include <cstdio>10 #include <cstring>11 #include <algorithm>12 #include <queue>13 #include <vector>14 #define MAX 1000215 #define INF (1<<30)16 #define ll long long17 using namespace std;18  19 int n,m,st,ed;20  21 typedef struct{22     int to,next,l;23     double p;24 }edge;25  26 edge e[MAX<<1];27 int p[MAX],tot;28 int dist[MAX];29 double pa[MAX];30 queue<int> q;31 bool vis[MAX];32  33 inline void add(int u,int v,int l,int per){34     e[tot].to=v; e[tot].l=l; e[tot].p=1-(per*1.0/100); e[tot].next=p[u]; p[u]=tot++;35 }36  37 void spfa(){38     for(int i=1;i<=n;i++) dist[i]=INF;39     memset(vis,0,sizeof(vis));40     while(!q.empty()) q.pop();41     dist[st]=0;42     pa[st]=1;43     vis[st]=1;44     q.push(st);45     while(!q.empty()){46         int u = q.front();47         q.pop();48         vis[u]=0;49         for(int i=p[u];i!=-1;i=e[i].next){50             if(e[i].l+dist[u]<dist[e[i].to]){51                 dist[e[i].to]=e[i].l+dist[u];52                 pa[e[i].to]=pa[u]*e[i].p;53                 if(!vis[e[i].to]){54                     vis[e[i].to]=1;55                     q.push(e[i].to);56                 }57             }else if(e[i].l+dist[u]==dist[e[i].to] && pa[e[i].to]<pa[u]*e[i].p){58                 pa[e[i].to]=pa[u]*e[i].p;59                 if(!vis[e[i].to]){60                     vis[e[i].to]=1;61                     q.push(e[i].to);62                 }63             }64         }65     }66 }67  68 int main()69 {70     int t,u,v,l,per;71     //freopen("data.txt","r",stdin);72     scanf("%d",&t);73     while(t--){74         scanf("%d %d",&n,&m);75         memset(p,-1,sizeof(p));76         tot=0;77         for(int i=0;i<m;i++){78             scanf("%d %d %d %d",&u,&v,&l,&per);79             add(u,v,l,per);80             add(v,u,l,per);81         }82         scanf("%d %d",&st,&ed);83         spfa();84         printf("%d %.6lf\n",dist[ed],1-pa[ed]);85     }86     return 0;87 }
/*Chasing Girl*/

 


联系
我们