• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# 一些最短路的题目

2周前 (05-03) 8次浏览

HDU1596
Problem Description
XX星球有很多城市，每个城市之间有一条或多条飞行通道，但是并不是所有的路都是很安全的，每一条路有一个安全系数s,s是在 0 和 1 间的实数(包括0，1)，一条从u 到 v 的通道P 的安全度为Safe§ = s(e1)*s(e2)…*s(ek) e1,e2,ek是P 上的边 ，现在8600 想出去旅游，面对这这么多的路，他想找一条最安全的路。但是8600 的数学不好，想请你帮忙 _

Input

Output

Sample Input
3
1 0.5 0.5
0.5 1 0.4
0.5 0.4 1
3
1 2
2 3
1 3

Sample Output
0.500
0.400
0.500

floyd算法

``````#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdlib>

using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define inf 0x3f3f3f3f
#define ll long long
int n;
double ave;
void init()
{
for(int i = 1;i <= n; i++)
for(int j = 1; j <= n; j++)
scanf("%lf",&ave[i][j]);
}
void floyd()
{
for(int k = 1;k <= n;k++){
for(int i = 1; i <= n ;i++){
for( int j = 1;j <= n; j++)
ave[i][j] = max(ave[i][j],ave[i][k]*ave[k][j]);
}
}
}
int main()
{   int q,a,b;
while(~scanf("%d",&n)){
init();
floyd();
scanf("%d",&q);
for(int i = 0 ;i < q;i++){
scanf("%d%d",&a,&b);
if(ave[a][b] == 0) cout<<"What a pity!"<<endl;
else printf("%.3lfn",ave[a][b]);
}
}
return 0;
}
``````

HDU1874
Problem Description

Input

Output

Sample Input
3 3
0 1 1
0 2 3
1 2 1
0 2
3 1
0 1 1
1 2

Sample Output
2
-1

``````#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdlib>

using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define inf 0x3f3f3f3f
int n,m,ave;
void floyd()
{
int k,i,j;
for(k = 1; k <= n;k++){
for(i = 1 ;i <=n ;i++){
for(j = 1;j <= n; j++){
if(ave[i][j]>ave[i][k]+ave[k][j])
ave[i][j] = ave[i][k]+ave[k][j];
}
}
}
}
int main()
{
int a,b,c;
while(cin>>n>>m){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
ave[i][j]= i==j?0:inf;
}
for(int i = 0 ;i < m ;i ++){
cin>>a>>b>>c;
a++;b++;
if(ave[a][b]>c)
ave[a][b] = ave[b][a] = c;
}
floyd();
cin>>a>>b;
a++;b++;
if(ave[a][b] != inf)
cout<<ave[a][b]<<endl;
else cout<<-1<<endl;
}
return 0;
}

``````

HDU2112
Problem Description

Input

note：一组数据中地名数不会超过150个。

Output

Sample Input
6
xiasha westlake
xiasha station 60
xiasha ShoppingCenterofHangZhou 30
station westlake 20
ShoppingCenterofHangZhou supermarket 10
xiasha supermarket 50
supermarket westlake 10
-1

Sample Output
50

Hint:
The best route is:
xiasha->ShoppingCenterofHangZhou->supermarket->westlake

――全剧终――

``````#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<cstdlib>

using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define inf 0x3f3f3f3f
int n,cnt,ave,vis,dis;
map<string,int>p;
string s,t;

int main()
{   IOS;
while(cin>>n&&n!=-1){
cnt = 0;
if(n == 0) {
cout<<0<<endl;
continue;
}
memset(ave,inf,sizeof(ave));
p.clear();
cin>>s>>t;
p[s] = ++cnt;
int start = p[s];
if(!p[t])
p[t] = ++cnt;
int end = p[t];

int c;
for(int i = 1;i <= n;i++){
cin>>s>>t>>c;
if(!p[s]) p[s] = ++cnt;
if(!p[t]) p[t] = ++cnt;
if(ave[p[s]][p[t]] > c) ave[p[s]][p[t]] = ave[p[t]][p[s]] = c;
}
if(start == end) {
cout<<0<<endl;
continue;
}
for(int i = 1;i <= cnt;i++){
if(i != start ) {
dis[i] = ave[start][i];
vis[i] = 1;
}
else {
dis[i] = 0;
vis[i] = 0;
}
}
for(int i = 1;i < cnt;i++){
int ans,k;
ans = inf;k = 1;
for(int j = 1;j <= cnt ;j++){
if(vis[j] && dis[j] < ans) {
ans = dis[j];
k = j;
}
}
vis[k] = 0;
for(int j = 1;j <= cnt;j++){
if(vis[j] && ans+ave[k][j] < dis[j]) dis[j] = ans + ave[k][j];
}

}
if(dis[end] == inf) cout<<-1<<endl;
else cout<<dis[end]<<endl;
}
return 0;
}

``````

HDU2680

Problem Description
One day , Kiki wants to visit one of her friends. As she is liable to carsickness , she wants to arrive at her friend’s home as soon as possible . Now give you a map of the city’s traffic route, and the stations which are near Kiki’s home so that she can take. You may suppose Kiki can change the bus at any station. Please find out the least time Kiki needs to spend. To make it easy, if the city have n bus stations ,the stations will been expressed as an integer 1,2,3…n.

Input
There are several test cases.
Each case begins with three integers n, m and s,(n<1000,m<20000,1=<s<=n) n stands for the number of bus stations in this city and m stands for the number of directed ways between bus stations .(Maybe there are several ways between two bus stations .) s stands for the bus station that near Kiki’s friend’s home.
Then follow m lines ,each line contains three integers p , q , t (0<t<=1000). means from station p to station q there is a way and it will costs t minutes .
Then a line with an integer w(0<w<n), means the number of stations Kiki can take at the beginning. Then follows w integers stands for these stations.

Output
The output contains one line for each data set : the least time Kiki needs to spend ,if it’s impossible to find such a route ,just output “-1”.

Sample Input
5 8 5
1 2 2
1 5 3
1 3 4
2 4 7
2 5 6
2 3 5
3 5 1
4 5 1
2
2 3
4 3 4
1 2 3
1 3 4
2 3 2
1
1

Sample Output
1
-1

``````#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<cstdlib>

using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define inf 0x3f3f3f3f
int n,m,s,ave,dis,vis;

int main()
{   int a,b,c;
IOS;
while(cin>>n>>m>>s){
n++;
memset(ave,inf,sizeof(ave));
for(int i = 1;i <= m;i++){
cin>>a>>b>>c;
if(ave[a][b] > c) ave[a][b] = c;//注意是单向
}
int w;
cin>>w;
for(int i = 1;i <= w;i++){
cin>>a;
ave[n][a] = 0;
}
for(int i = 1;i <= n;i++){
if(i != n) {
dis[i] = ave[n][i];
vis[i] = 1;
}
else {
dis[i] = 0;
vis[i] = 0;
}
}
for(int i = 1; i <= n; i++){
int k,ans;
ans = inf;
for(int j = 1;j <= n;j++){
if(vis[j] && dis[j] < ans) {
ans = dis[j];
k = j;
}
}
if(ans == inf) break;
vis[k] = 0;
for(int j = 1;j <= n;j++){
if(vis[j] && ans + ave[k][j] < dis[j]) dis[j] = ans + ave[k][j];
}
}
if(dis[s] != inf)
cout<<dis[s]<<endl;
else cout<<-1<<endl;
}
return 0;
}

``````

HDU1690
Problem Description
Because of the huge population of China, public transportation is very important. Bus is an important transportation method in traditional public transportation system. And it’s still playing an important role even now.
The bus system of City X is quite strange. Unlike other city’s system, the cost of ticket is calculated based on the distance between the two stations. Here is a list which describes the relationship between the distance and the cost.

Your neighbor is a person who is a really miser. He asked you to help him to calculate the minimum cost between the two stations he listed. Can you solve this problem for him?
To simplify this problem, you can assume that all the stations are located on a straight line. We use x-coordinates to describe the stations’ positions.

Input
The input consists of several test cases. There is a single number above all, the number of cases. There are no more than 20 cases.
Each case contains eight integers on the first line, which are L1, L2, L3, L4, C1, C2, C3, C4, each number is non-negative and not larger than 1,000,000,000. You can also assume that L1<=L2<=L3<=L4.
Two integers, n and m, are given next, representing the number of the stations and questions. Each of the next n lines contains one integer, representing the x-coordinate of the ith station. Each of the next m lines contains two integers, representing the start point and the destination.
In all of the questions, the start point will be different from the destination.
For each case,2<=N<=100,0<=M<=500, each x-coordinate is between -1,000,000,000 and 1,000,000,000, and no two x-coordinates will have the same value.

Output
For each question, if the two stations are attainable, print the minimum cost between them. Otherwise, print “Station X and station Y are not attainable.” Use the format in the sample.

Sample Input
2
1 2 3 4 1 3 5 7
4 2
1
2
3
4
1 4
4 1
1 2 3 4 1 3 5 7
4 1
1
2
3
10
1 4

Sample Output
Case 1:
The minimum cost between station 1 and station 4 is 3.
The minimum cost between station 4 and station 1 is 3.
Case 2:
Station 1 and station 4 are not attainable.

``````#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<cstdlib>

using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define inf 0x3f3f3f3f3f3f3f3f
#define ll long long
ll l1,l2,l3,l4,c1,c2,c3,c4,n,m,k;
ll ave,dis;

int main()
{   IOS;
int nn,op;
cin>>nn;
op = 1;
while(nn--){
cin>>l1>>l2>>l3>>l4>>c1>>c2>>c3>>c4;
cin>>n>>m;
for(int i = 1;i <= n;i++){
cin>>dis[i];
}
for(int i = 1;i <= n;i++){
for(int j = i;j <= n;j++){
k = abs(dis[i] - dis[j]);
if(k == 0) ave[i][j] = ave[j][i] = 0;
else if(k <= l1) ave[i][j] = ave[j][i] = c1;
else if(k <= l2) ave[i][j] = ave[j][i] = c2;
else if(k <= l3) ave[i][j] = ave[j][i] = c3;
else if(k <= l4) ave[i][j] = ave[j][i] = c4;
else ave[i][j] = ave[j][i] = inf;
}
}
for(int k = 1;k <= n;k++)
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++)
ave[i][j] = min(ave[i][j],ave[i][k] + ave[k][j]);
printf("Case %d:n",op++);
ll a,b;
for(int i = 1;i <= m;i++){
cin>>a>>b;
if(ave[a][b] == inf)
printf("Station %lld and station %lld are not attainable.n",a,b);
else  printf("The minimum cost between station %lld and station %lld is %lld.n",a,b,ave[a][b]);
}
}
return 0;
}

``````

POJ3268
Description

One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1…N is going to attend the big cow party to be held at farm #X (1 ≤ X ≤ N). A total of M (1 ≤ M ≤ 100,000) unidirectional (one-way roads connects pairs of farms; road i requires Ti (1 ≤ Ti ≤ 100) units of time to traverse.

Each cow must walk to the party and, when the party is over, return to her farm. Each cow is lazy and thus picks an optimal route with the shortest time. A cow’s return route might be different from her original route to the party since roads are one-way.

Of all the cows, what is the longest amount of time a cow must spend walking to the party and back?

Input

Line 1: Three space-separated integers, respectively: N, M, and X
Lines 2…M+1: Line i+1 describes road i with three space-separated integers: Ai, Bi, and Ti. The described road runs from farm Ai to farm Bi, requiring Ti time units to traverse.
Output

Line 1: One integer: the maximum of time any one cow must walk.
Sample Input

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3
Sample Output

10
Hint

Cow 4 proceeds directly to the party (3 units) and returns via farms 1 and 3 (7 units), for a total of 10 time units.
Source

``````#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdlib>

using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define inf 0x3f3f3f3f
#define ll long long
int n,m,x,ave,dis,flag;
void dij(int start)
{
for(int i = 1; i <= n; i++){
if(i != start){
dis[i] = ave[start][i];
flag[i] = 1;
}
else {
dis[i] = flag[i] = 0;
}
}
int num = 1;
while(num < n){
int ans,k;
ans = inf;
for(int i = 1;i <= n;i++){
if(flag[i] && dis[i] < ans) {
ans = dis[i];
k = i;
}
}
flag[k] = 0;
for(int i = 1;i <= n;i++){
if(flag[i] && dis[i] > dis[k] + ave[k][i]) dis[i] = dis[k] + ave[k][i];
}
num++;
}
}
int main()
{   IOS;
cin>>n>>m>>x;
memset(ave,inf,sizeof(ave));
for(int i = 1;i <= m;i++){
int a,b,c;
cin>>a>>b>>c;
if(ave[a][b] > c) ave[a][b] = c;
}
dij(x);
int ma;
for(int i = 1;i <= n;i++){
ma[i] = dis[i];
for(int j = i+1;j <= n;j++) swap(ave[i][j],ave[j][i]);
}
dij(x);
int ans = 0;
for(int i = 1;i <= n;i++){
if(ma[i] + dis[i] > ans) ans = ma[i] + dis[i];
}
cout<<ans<<endl;
return 0;
}

``````