ACDream - Chasing Girl

先上题目：

Chasing Girl

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

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

Sample Output

5 0.650000

5 0.600000

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

上代码：

 /*

 * this code is made by sineatos

 * Problem: 1180

 * Verdict: Accepted

 * Submission Date: 2014-07-31 15:23:49

 * Time: 228MS

 * Memory: 1884KB

 */

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <queue>

 #include <vector>

 #define MAX 10002

 #define INF (1<<30)

 #define ll long long

 using namespace std;

 int n,m,st,ed;

 typedef struct{

     int to,next,l;

     double p;

 }edge;

 edge e[MAX<<];

 int p[MAX],tot;

 int dist[MAX];

 double pa[MAX];

 queue<int> q;

 bool vis[MAX];

 inline void add(int u,int v,int l,int per){

     e[tot].to=v; e[tot].l=l; e[tot].p=-(per*1.0/); e[tot].next=p[u]; p[u]=tot++;

 }

 void spfa(){

     for(int i=;i<=n;i++) dist[i]=INF;

     memset(vis,,sizeof(vis));

     while(!q.empty()) q.pop();

     dist[st]=;

     pa[st]=;

     vis[st]=;

     q.push(st);

     while(!q.empty()){

         int u = q.front();

         q.pop();

         vis[u]=;

         for(int i=p[u];i!=-;i=e[i].next){

             if(e[i].l+dist[u]<dist[e[i].to]){

                 dist[e[i].to]=e[i].l+dist[u];

                 pa[e[i].to]=pa[u]*e[i].p;

                 if(!vis[e[i].to]){

                     vis[e[i].to]=;

                     q.push(e[i].to);

                 }

             }else if(e[i].l+dist[u]==dist[e[i].to] && pa[e[i].to]<pa[u]*e[i].p){

                 pa[e[i].to]=pa[u]*e[i].p;

                 if(!vis[e[i].to]){

                     vis[e[i].to]=;

                     q.push(e[i].to);

                 }

             }

         }

     }

 }

 int main()

 {

     int t,u,v,l,per;

     //freopen("data.txt","r",stdin);

     scanf("%d",&t);

     while(t--){

         scanf("%d %d",&n,&m);

         memset(p,-,sizeof(p));

         tot=;

         for(int i=;i<m;i++){

             scanf("%d %d %d %d",&u,&v,&l,&per);

             add(u,v,l,per);

             add(v,u,l,per);

         }

         scanf("%d %d",&st,&ed);

         spfa();

         printf("%d %.6lf\n",dist[ed],-pa[ed]);

     }

     return ;

 }

/*Chasing Girl*/

巴特西