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
輸入包括多個測驗實體，每個實體包括：
第一行：n，n表示城市的個數n<=1000;
接著是一個n*n的矩陣表示兩個城市之間的安全系數，(0可以理解為那兩個城市之間沒有直接的通道)
接著是Q個8600要旅游的路線,每行有兩個數字，表示8600所在的城市和要去的城市
Output
如果86無法達到他的目的地，輸出"What a pity!",
其他的輸出這兩個城市之間的最安全道路的安全系數,保留三位小數，
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[1005][1005];
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("%.3lf\n",ave[a][b]);
}
}
return 0;
}
HDU1874
Problem Description
某省自從實行了很多年的暢通工程計劃后，終于修建了很多路，不過路多了也不好，每次要從一個城鎮到另一個城鎮時，都有許多種道路方案可以選擇，而某些方案要比另一些方案行走的距離要短很多，這讓行人很困擾，
現在，已知起點和終點，請你計算出要從起點到終點，最短需要行走多少距離，
Input
本題目包含多組資料，請處理到檔案結束，
每組資料第一行包含兩個正整數N和M(0<N<200,0<M<1000)，分別代表現有城鎮的數目和已修建的道路的數目，城鎮分別以0～N-1編號，
接下來是M行道路資訊，每一行有三個整數A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城鎮A和城鎮B之間有一條長度為X的雙向道路，
再接下一行有兩個整數S,T(0<=S,T<N)，分別代表起點和終點，
Output
對于每組資料，請在一行里輸出最短需要行走的距離，如果不存在從S到T的路線，就輸出-1.
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[205][205];
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
經過錦囊相助，海東集團終于度過了危機，從此，HDU的發展就一直順風順水，到了2050年，集團已經相當規模了，據說進入了錢江肉絲經濟開發區500強，這時候，XHD夫婦也退居了二線，并在風景秀美的諸暨市浬浦鎮陶姚村買了個房子，開始安度晚年了，
這樣住了一段時間，徐總對當地的交通還是不太了解，有時很郁悶，想去一個地方又不知道應該乘什么公交車，在什么地方轉車，在什么地方下車（其實徐總自己有車，卻一定要與民同樂，這就是徐總的性格），
徐總經常會問蹩腳的英文問路：“Can you help me?”，看著他那迷茫而又無助的眼神，熱心的你能幫幫他嗎？
請幫助他用最短的時間到達目的地（假設每一路公交車都只在起點站和終點站停，而且隨時都會開），
Input
輸入資料有多組，每組的第一行是公交車的總數N(0<=N<=10000)；
第二行有徐總的所在地start，他的目的地end；
接著有n行，每行有站名s，站名e，以及從s到e的時間整數t(0<t<100)(每個地名是一個長度不超過30的字串)，
note：一組資料中地名數不會超過150個，
如果N==-1，表示輸入結束，
Output
如果徐總能到達目的地，輸出最短的時間；否則，輸出“-1”，
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[155][155],vis[155],dis[155];
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[1010][1010],dis[1010],vis[1010];
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[110][110],dis[110];
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[1005][1005],dis[1005],flag[1005];
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[1005];
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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/282582.html
標籤：其他
上一篇：**用歐幾里得提出的輾轉相除法求兩個數的最大公約數**
下一篇：redis6 安裝和可視化工具