Dijsktra就可以了，概率用相乘的，其他没什么区别。
{dy}次用的是priority_queue<vectex_t *, ...>，然后后来出现各种莫名其妙的问题，郁闷一下午，刚才才发现修改iter->dest->dist的时候可能队列里面的元素的dist也被修改了，然后队列就xx乱掉了，所以就会出问题，改成priority_queue<vectex_t, ...>就好了。
有关于一个顶点多次入队列：显然必然有一个dist最小的顶点先弹出来（这个顶点的dist就是src到这个点的最短路径），然后这个顶点更新了它的所有邻接节点并把它们压入队列（如果邻接节点的dist已经是最短路则显然不会被更新），等第二次同一个节点（但是dist较大）弹出来的时候，就不能去更新任何节点的dist了，所以实际上就是一个空的loop，不会影响结果。
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <iterator>
#include <functional>
#include <string>
#include <queue>
using namespace std;
struct edge_t {
struct vectex_t *src;
struct vectex_t *dest;
int weight;
edge_t *next;
};
struct vectex_t{
double dist;
edge_t *edges;
};
edge_t edges[10000];
edge_t *end_of_edges;
vectex_t vectices[100];
int nr_vectexs;
struct comp_cls {
bool operator () (vectex_t const &vptr1, vectex_t const &vptr2) const {
return vptr1.dist < vptr2.dist;
}
};
inline
void
add_edge(int src, int dest, int weight)
{
end_of_edges->next = vectices[src].edges;
end_of_edges->src = &vectices[src];
end_of_edges->dest = &vectices[dest];
end_of_edges->weight = weight;
vectices[src].edges = end_of_edges++;
return;
}
double
dijkstra(void)
{
priority_queue<vectex_t, vector<vectex_t>, comp_cls> pq;
vectices[0].dist = 1;
pq.push(vectices[0]);
while (pq.size()) {
vectex_t current(pq.top());
pq.pop();
for (edge_t *iter = current.edges; iter; iter = iter->next) {
if (iter->dest->dist < current.dist * iter->weight / 100) {
iter->dest->dist = current.dist * iter->weight / 100;
pq.push(*iter->dest);
}
}
}
return vectices[nr_vectexs - 1].dist * 100;
}
bool
solve_prob(void)
{
int nr_edges;
end_of_edges = edges;
memset(vectices, 0, sizeof(vectices));
cin >> nr_vectexs;
if (!nr_vectexs) {
return false;
}
cin >> nr_edges;
for (int i = 0; i != nr_edges; ++i) {
int src, dest, weight;
cin >> src >> dest >> weight;
--src;
--dest;
add_edge(src, dest, weight);
add_edge(dest, src, weight);
}
for (int i = 0; i != nr_vectexs; ++i) {
vectices[i].dist = 0;
}
cout << fixed << setprecision(6) << dijkstra() << " percent" << endl;
return true;
}
int
main()
{
ios::sync_with_stdio(false);
while (solve_prob()) {
;
}
return 0;
}
