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
2 4 4 1 2 1 50 2 3 2 50 1 4 5 20 4 3 3 30 2 4 4 4 1 2 1 50 2 3 2 50 1 4 4 20 4 3 3 30 2 4
Sample Output
5 0.650000 5 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 10002 15 #define INF (1<<30) 16 #define ll long long 17 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 }