把 #P4779. 【模板】单源最短路径（标准版）（题解）的代码复制过来，然后把入队条件和输出改改就行了

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2005,M = 4022035;	// 改这里

// 链式前向星 
struct edge{
	int v,w,prev;
}edges[M];
int tail[N],tot;
void add_edge(int u,int v,int w){
	edges[++tot] = {v,w,tail[u]};
	tail[u] = tot;
}

int n,m,s,e;
double dis[N];
bool f[N];
void dkstr(){
	priority_queue<pair<double,int>> q;
	q.push({-100,s});
	while (!q.empty()){
		int u = q.top().second;
		q.pop();
		if (f[u])	continue;
		f[u] = 1;
		for (int i = tail[u];i;i = edges[i].prev){
			int v = edges[i].v,w = edges[i].w;
			// 改这里
			if (!f[v] && dis[u] / (1 - w / 100.0) < dis[v]){
				dis[v] = dis[u] / (1 - w / 100.0);
				q.push({-dis[v],v});
			}
		}
	}
}
int main(int argc, char **argv){
	memset(dis,0x7f,sizeof(dis));

	cin >> n >> m;
	for (int i = 0;i < m;i++){
		int u,v,w;
		cin >> u >> v >> w;
		add_edge(u,v,w);
		add_edge(v,u,w);
	}
	cin >> s >> e;
	dis[s] = 100;

	dkstr();
	printf("%.8lf",dis[e]);	// 改这里
	return 0;
}

题解

求一个点到另一个点的最小花费

思路

将最短路的更新部分改一改就可以了

注意M的值开大点

代码

#include<iostream>
#include<queue>
#include<cstring>
#include<utility>
#define N 11451
#define M 4514114//开大点
#define INF 0x3ffffffff
using namespace std;
int n,m,a,b;
struct ed
{
    int u,v,w;
    int next;
};
ed g[M];
int to=0,h[N];
double dis[N]={0};
int vis[N]={0};
priority_queue<pair<double,int> ,vector<pair<double,int> >,greater<pair<double,int> > >q;
void dijkstra()
{
    while(!q.empty())
    {
        int u=q.top().second;
        q.pop();
        if(vis[u])
            continue;
        vis[u]=1;
        for(int i=h[u];i;i=g[i].next)
        {
            int v=g[i].v;
            double l=dis[u]/(1-g[i].w*0.01);//注意公式
            if(l<dis[v] && !vis[v])
            {
                dis[v]=l;
                q.push({l,v});
            }
        }
    }
}
void push(int u,int v,int w)
{
    g[++to]={u,v,w};
    g[to].next=h[u];
    h[u]=to;
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        push(u,v,w);
        push(v,u,w);//双向
    }
    cin>>a>>b;
    memset(dis,0x7f,sizeof(dis));
    dis[a]=100;
    q.push({100,a});
    dijkstra();
    printf("%.8lf",dis[b]);//输出
    return 0;//完结散花
}

#include <bits/stdc++.h>

using namespace std;
const int maxn = 2e3 + 5, INF = 0x3f3f3f3f;
int n, m, s, a ,b;
struct node{
	int v;
	double w;
};
vector<node> g[maxn];
priority_queue<pair<double, int>> q;
double dis[maxn];
bool vis[maxn];
void dj(int s){
	memset(dis, 0, sizeof(dis));
	memset(vis, 0, sizeof(vis));
	dis[s] = 1;
	q.push(make_pair(0, s));
	while (!q.empty()){
		int u = q.top().second;
		q.pop();
		if (vis[u]) continue;
		vis[u] = true;
		for (auto p : g[u]){
			if (dis[u] * p.w > dis[p.v]){
				dis[p.v] = dis[u] * p.w;
				q.push(make_pair(dis[p.v], p.v));
			}
		}
	}
}
int main(){
	cin >> n >> m;
	for (int i = 1; i <= m; i++){
		int u, v;
		double w;
		cin >> u >> v >> w;
		g[u].push_back({v,1 -  w / 100});
		g[v].push_back({u,1 -  w / 100});
	}
	cin >> a >> b;
	dj(b);
	cout << fixed << setprecision(8) << (double)(100 / dis[a]) << endl; 
	return 0;
}