题目描述
H 城是一个旅游胜地，每年都有成千上万的人前来观光。
为方便游客，巴士公司在各个旅游景点及宾馆，饭店等地都设置了巴士站并开通了一些单程巴士线路。
每条单程巴士线路从某个巴士站出发，依次途经若干个巴士站，最终到达终点巴士站。
一名旅客最近到 H 城旅游，他很想去 S公园游玩，但如果从他所在的饭店没有一路巴士可以直接到达 S 公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士，这样换乘几次后到达 S 公园。
现在用整数 1,2,…N给 H 城的所有的巴士站编号，约定这名旅客所在饭店的巴士站编号为 1，S 公园巴士站的编号为 N。
写一个程序，帮助这名旅客寻找一个最优乘车方案，使他在从饭店乘车到 S 公园的过程中换乘的次数最少。
输入格式
第一行有两个数字 M 和 N，表示开通了 M 条单程巴士线路，总共有 N 个车站。
从第二行到第 M+1 行依次给出了第 11 条到第 M 条巴士线路的信息，其中第 i+1 行给出的是第 i 条巴士线路的信息，从左至右按运行顺序依次给出了该线路上的所有站号，相邻两个站号之间用一个空格隔开。
输出格式
共一行，如果无法乘巴士从饭店到达 S 公园，则输出
NO，否则输出最少换乘次数，换乘次数为 0 表示不需换车即可到达。数据范围
1≤M≤100,
2≤N≤500输入样例：
3 7 6 7 4 7 3 6 2 1 3 5输出样例：
2
C++代码：
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<sstream>
using namespace std;
typedef pair<int,int> PII;
const int N=3e5+5;
int e[N],ne[N],h[N],stop[N],dist[N],idx,n,m;
bool st[N];
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void Dijkstra()
{
memset(dist,0x3f,sizeof dist);
dist[1]=0;
priority_queue<PII,vector<PII>,greater<PII>> heap;
heap.push({0,1});
while(heap.size())
{
auto it=heap.top();heap.pop();
int distance=it.first,t=it.second;
if(st[t]) continue;
st[t]=true;
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
if(!st[j]&&dist[j]>distance+1)
{
dist[j]=distance+1;
heap.push({dist[j],j});
}
}
}
}
int main()
{
cin>>m>>n;
getchar();
memset(h,-1,sizeof h);
while(m--)
{
string line;
getline(cin,line);
stringstream ssin(line);
int cnt=0,p;
while(ssin>>p) stop[cnt++]=p;
for(int i=0;i<cnt;i++)
for(int j=i+1;j<cnt;j++)
add(stop[i],stop[j]);
}
Dijkstra();
if(dist[n]==0x3f3f3f3f) cout<<"NO";
else cout<<max(dist[n]-1,0);
return 0;
}题目描述
在 n 个人中，某些人的银行账号之间可以互相转账。
这些人之间转账的手续费各不相同。
给定这些人之间转账时需要从转账金额里扣除百分之几的手续费，请问 A 最少需要多少钱使得转账后 B 收到 100 元。
输入格式
第一行输入两个正整数 n,m，分别表示总人数和可以互相转账的人的对数。
以下 m 行每行输入三个正整数 x,y,z，表示标号为 x 的人和标号为 y 的人之间互相转账需要扣除 z%的手续费 ( z<100 )。
最后一行输入两个正整数 A,B。
数据保证 A 与 B 之间可以直接或间接地转账。
输出格式
输出 A 使得 B 到账 100 元最少需要的总费用。
精确到小数点后 8 位。
数据范围
1≤n≤2000,
m≤10^5输入样例：
3 3 1 2 1 2 3 2 1 3 3 1 3输出样例：
103.07153164
思路： A*(1-z1)*(1-z2).....(1-zn)=100，A要最小则（1-z1)*（1-z2).....(1-zn)要最大，所以可以用Dijkstra算法来求最大路径
C++代码：
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<double,int> PDI;
const int N=2e5+5;
int e[N],ne[N],h[N],idx;double w[N];
double dist[N];
int n,m,A,B;
bool st[N];
void add(int a,int b,double c)
{
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void Dijkstra()
{
memset(dist,0,sizeof dist);
dist[A]=1.0;
priority_queue<PDI> heap;
heap.push({1.0,A});
while(heap.size())
{
auto it=heap.top();heap.pop();
double distance=it.first;int t=it.second;
if(st[t]) continue;
st[t]=true;
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
if(!st[j]&&dist[j]<distance*w[i])
{
dist[j]=distance*w[i];
heap.push({dist[j],j});
}
}
}
return ;
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof h);
while(m--)
{
int a,b;
double c;cin>>a>>b>>c;
c=(100.0-c)/100;
add(a,b,c),add(b,a,c);
}
cin>>A>>B;
Dijkstra();
printf("%.8lf",100/dist[B]);
return 0;
}