DES:给出起点和终点。给出所有小岛的编号。所有路径的起始点。和遇到怪物的概率。要求在最短路的条件下维护遇见怪物的概率最小的路径。就是用 SPFA算法。每条路的权值设为1。最短路即为途径的岛数最少。同时要用pre数组维护每个点的前驱。最后递归输出所走路径。把p变为不遇见怪物的概率， 即为维护p最大。就是把原来的SPFA里的判断多加一条，如果权值相等判断概率，选择概率大的一条。
注意。这是无向图。本来觉得没有影响。很幸福的WA了。确实是。给你a->b的，就代表可以从b->a。而不是简单的可以往返。
不知道用邻接表和邻接矩阵时间差大不大。这里用了邻接表
#include<stdio.h> #include<iostream> #include<string.h> using namespace std; #include<queue> #define N 100010 #define inf 0x1f1f1f1f int low[N]; //存储源点到每个顶点的最短距离值 bool in_que[N]; //标记一个点是否已在队列中 int cnt[N]; //记录每个点的入队次数，来判断是否出现负环 int pre[N]; // 记录每个点的前驱。即记录源点到每个点的最短路径本身。 int head[N]; //邻接矩阵的表头节点 double p[N]; //存储最短路的情况下。到每个点的p最大。 int n, m; int h; bool flag = true; struct Edge { int v, w, next; double p; }edge[N<<1]; void addEdge(int a, int b, double c) { edge[h].v = b; edge[h].w = 1; edge[h].p = c; edge[h].next = head[a]; head[a] = h++; } void spfa(int s) { for (int i=0; i<=n; ++i) { p[i] = 0; low[i] = inf; } memset(pre, -1, sizeof(pre)); memset(in_que, 0, sizeof(in_que)); queue<int>q; in_que[s] = 1; low[s] = 1; p[s] = 1; //没有怪物 q.push(s); while(!q.empty()) { int x = q.front(); q.pop(); in_que[x] = 0; for (int i=head[x]; i!=-1; i=edge[i].next) { int v = edge[i].v; if (low[v] > low[x]+1) { low[v] = low[x] + 1; p[v] = p[x]*edge[i].p; pre[v] = x; if (!in_que[v]) { in_que[v] = 1; q.push(v); } } else if (low[v] == low[x] + 1) { if (p[v] < p[x]*edge[i].p) { p[v] = p[x]*edge[i].p; pre[v] = x; if (!in_que[v]) { in_que[v] = 1; q.push(v); } } } } } return; } void output(int r) { if (pre[r] != -1) output(pre[r]); if (flag) flag = false; else putchar(' '); printf("%d", r); } int main() { int s, t; int a, b; double c; while(~scanf("%d%d", &n, &m)) { scanf("%d%d", &s, &t); h = 0; memset(head, -1, sizeof(head)); for (int i=0; i<m; ++i) { scanf("%d%d%lf", &a, &b, &c); c = (1-c/100); addEdge(a, b, c); addEdge(b, a, c); } spfa(s); printf("%d %.6lf ", low[t], 1-p[t]); flag = true; output(t); puts(""); } return 0; }