首頁猿問一道ACM題目

一道ACM題目

C C++

慕移動0678692 2016-04-26 22:18:29

Description神秘的海洋，驚險(xiǎn)的探險(xiǎn)之路，打撈海底寶藏，激烈的海戰(zhàn)，海盜劫富等等。加勒比海盜，你知道吧？杰克船長駕駛著自己的的戰(zhàn)船黑珍珠1號要征服各個(gè)海島的海盜，最后成為海盜王。這是一個(gè)由海洋、島嶼和海盜組成的危險(xiǎn)世界。杰克船長準(zhǔn)備從自己所占領(lǐng)的島嶼A開始征程，逐個(gè)去占領(lǐng)每一個(gè)島嶼。面對危險(xiǎn)重重的海洋與詭譎的對手，如何憑借智慧與運(yùn)氣，建立起一個(gè)強(qiáng)大的海盜帝國。?杰克船長手頭有一張整個(gè)海域的海圖，上面詳細(xì)地記錄了各個(gè)海嶼的位置，以及海嶼之間的通航路線。但他發(fā)現(xiàn)，有的航海路線太危險(xiǎn)了，杰克船長的戰(zhàn)船很難直接通過，他必須想方設(shè)法繞道航行；還有的島嶼根本到達(dá)不了。?杰克船長現(xiàn)在想把航行的危險(xiǎn)程度降到最小。具體地來說，就是杰克船長提出若干個(gè)詢問，他想知道從島嶼A 到島嶼B 有沒有行駛航線，若有的話，所經(jīng)過的航線，危險(xiǎn)程度最小可能是多少。Input第1行: N M 表示有N個(gè)島嶼，M條直航路線?第2~M+1行： A B V 表示從島嶼A到島嶼B的航海路線的危險(xiǎn)程度值為V。?接下面一行： Q 表示詢問的次數(shù)。?之后有Q個(gè)行： A B 表示詢問從島嶼A 到島嶼B 所經(jīng)過的航線，危險(xiǎn)程度最小值?1Output對于每個(gè)詢問，輸出占一行，一個(gè)整數(shù)，表示從島嶼A 到島嶼B 所經(jīng)過的航線，危險(xiǎn)程度最小值；若從島嶼A 無法到達(dá)島嶼B，則輸出-1。Sample Input10 8?1 2 5?1 3 2?2 3 11?2 4 6?2 4 4?6 7 10?6 10 5?10 7 2?5?2 3?1 4?3 7?6 7?8 3Sample Output5?5?-1?5?-1

查看完整描述

2 回答

已采納

qq___524

TA貢獻(xiàn)171條經(jīng)驗(yàn) 獲得超74個(gè)贊

#include?<bits/stdc++.h>?
#define?N?110
#define?ll?long?long
#define?MAX?111111
using?namespace?std;
int?g[N][N],?n,?m,?dis[N];
bool?flag[N];
int?prim(int?src,?int?des){
????int?i,?j,?ans?=?-1;
????????for?(i?=?1;?i?<=?n;?i++){
????????dis[i]?=?g[src][i];
????????flag[i]?=?false;
????}
????flag[src]?=?true;????for?(i?=?1;?i?<?n;?i++){????????int?mindist?=?MAX;????????int?u?=?-1;????????for?(j?=?1;?j?<=?n;?j++){????????????if?(!flag[j]?&&?mindist?>?dis[j]){
????????????????u?=?j;
????????????????mindist?=?dis[j];
????????????}
????????}????????if?(u?==?-1){????????????break;
????????}
????????flag[u]?=?true;
????????ans?=?max(ans,?mindist);????????if?(u?==?des){????????????return?ans;
????????}????????for?(j?=?1;?j?<=?n;?j++){????????????if?(!flag[j]?&&?dis[j]?>?g[u][j]){
????????????????dis[j]?=??g[u][j];
????????????}
????????}
????}????return?-1;
}int?main(){#ifndef?ONLINE_JUDGE
????freopen("1.txt",?"r",?stdin);#endif??
????int?i,?j,?k,?a,?b,?v,?q;????while(~scanf("%d%d",?&n,?&m)){????????for?(i?=?0;?i?<=?n;?i++){????????????for?(j?=?0;?j?<=?n;?j++){
????????????????g[i][j]?=?MAX;
????????????}
????????????g[i][i]?=?0;
????????}????????for?(i?=?0;?i?<?m;?i++){????????????scanf("%d%d%d",?&a,?&b,?&v);
????????????g[a][b]=?g[b][a]?=?min(g[a][b],?v);
????????}????????scanf("%d",?&q);????????while(q--){????????????scanf("%d%d",?&a,?&b);????????????printf("%d\n",?prim(a,?b));
????????}

????}????return?0;
}

最小生成樹問題

反對回復(fù) 2016-04-26