題目描述

“小兒么小二郎，背著那炸彈炸學(xué)校，不怕那太陽曬，也不怕那風(fēng)雨狂。”估計(jì)這首歌我們大家都耳熟能詳了。
于是就有一群小學(xué)生們商量著炸學(xué)校。要把本市的小學(xué)的都給炸掉。于是他們商量好了一個(gè)出發(fā)點(diǎn)source與集合點(diǎn)sink。然后有無數(shù)個(gè)小學(xué)生，n-2個(gè)學(xué)校，每個(gè)小學(xué)生都從出發(fā)點(diǎn)出發(fā)，負(fù)責(zé)背著一個(gè)炸彈，然后把炸彈偷偷放置在一個(gè)學(xué)校里，然后返回到集合點(diǎn)。 由于這群小學(xué)生們還急著回去玩擼啊擼，所以他們想盡快把所有學(xué)校都炸完。這里有m條無向路，每條路都連接著u和v這兩個(gè)學(xué)校，經(jīng)過這條路的時(shí)間花費(fèi)為t。這些小學(xué)生只能從這些路中經(jīng)過。他們同時(shí)從出發(fā)點(diǎn)出發(fā)，他們想知道炸完所有學(xué)校并且都回到集合點(diǎn)的最少需要多長時(shí)間。

輸入

第一行為一個(gè)整數(shù)T，表示T組測試數(shù)據(jù)。

第二行為整數(shù)n（3<=n<=1000），代表學(xué)校的數(shù)量（包括出發(fā)點(diǎn)和集合點(diǎn)），還有整數(shù)m（m<10^5），表示有多少條無向路。

然后接下來是m行，每一行的三個(gè)整數(shù)分別是u，v，t（0<=u，v，?u！=v，?0<=t<=10^5）

然后給出兩個(gè)整數(shù)source和sink，分別代表出發(fā)點(diǎn)和集合點(diǎn)。（0<=source，sink）。

輸入數(shù)據(jù)保證可以炸毀所有學(xué)校，并且可以到達(dá)集合點(diǎn)。不保證沒有重邊。

輸出：

輸出

對(duì)于第x組數(shù)據(jù)輸出一行“Case #x：”，然后是一個(gè)整數(shù)表示最少需要的時(shí)間。

示例輸入

1 5 5 1 0 1 1 2 3 1 3 3 4 2 2 3 4 1 4 2

示例輸出

Case #1: 9

提示

兩次最短路算法，從出發(fā)點(diǎn)到各學(xué)校和從集合點(diǎn)到各學(xué)校
#include <iostream> #include <cstdio> #include <cstring>using namespace std;const int inf=1<<28;int mp[1000][1000]; int vis[1000]; int dis[2][1000];void djs(int s,int n,int x) {int i,j;memset(vis,0,sizeof(vis));for(i=0;i<n;i++)dis[x][i]=mp[s][i];vis[s]=1;int k=s;for(i=1;i<n;i++){for(j=0;j<n;j++){if(!vis[j]&&dis[x][j]>dis[x][k]+mp[k][j])dis[x][j]=dis[x][k]+mp[k][j];}int mini=inf;for(j=0;j<n;j++){if(!vis[j]&&mini>dis[x][j])mini=dis[x][k=j];}vis[k]=1;} }int main() {int r,n,m,i,j,k;int u,v,t;int s,e;scanf("%d",&r);for(k=1;k<=r;k++){scanf("%d%d",&n,&m);for(i=0;i<n;i++)for(j=0;j<n;j++){if(i==j)mp[i][j]=0;elsemp[i][j]=inf;}for(i=0;i<m;i++){scanf("%d%d%d",&u,&v,&t);if(mp[u][v]>t) //可能有重邊，取用時(shí)最少的一條{mp[u][v]=t;mp[v][u]=t;}}scanf("%d%d",&s,&e);djs(s,n,0); //0和1表示從出發(fā)點(diǎn)到各學(xué)校和從集合點(diǎn)到各學(xué)校djs(e,n,1);int maxi=0;for(i=0;i<n;i++)maxi=max(maxi,dis[0][i]+dis[1][i]); //所有學(xué)生同時(shí)出發(fā)，用時(shí)最長的學(xué)生從出發(fā)點(diǎn)到達(dá)了集合點(diǎn)printf("Case #%d: %d\n",k,maxi); //那其他學(xué)生也到達(dá)了集合點(diǎn)}return 0; }

總結(jié)

以上是生活随笔為你收集整理的SDUTOJ 3034 ——炸学校的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。