洛谷 P2951 [USACO09OPEN]捉迷藏Hide and Seek

題目描述

Bessie is playing hide and seek (a game in which a number of players hide and a single player (the seeker) attempts to find them after which various penalties and rewards are assessed; much fun usually ensues).

She is trying to figure out in which of N (2 <= N <= 20,000) barns conveniently numbered 1..N she should hide. She knows that FJ (the seeker) starts out in barn 1. All the barns are connected by M (1 <= M <= 50,000) bidirectional paths with endpoints A_i and B_i (1 <= A_i <= N; 1 <= B_i <= N; A_i != B_i); it is possible to reach any barn from any other through the paths.

Bessie decides that it will be safest to hide in the barn that has the greatest distance from barn 1 (the distance between two barns is the smallest number of paths that one must traverse to get from one to the other). Help Bessie figure out the best barn in which to hide.

奶牛貝西和農夫約翰(FJ)玩捉迷藏,現在有N個谷倉,FJ開始在第一個谷倉,貝西為了不讓FJ找到她,當然要藏在距離第一個谷倉最遠的那個谷倉了。現在告訴你N個谷倉,和M個兩兩谷倉間的“無向邊”。每兩個倉谷間當然會有最短路徑,現在要求距離第一個谷倉(FJ那里)最遠的谷倉是哪個(所謂最遠就是距離第一個谷倉最大的最短路徑)?如有多個則輸出編號最小的。以及求這最遠距離是多少,和有幾個這樣的谷倉距離第一個谷倉那么遠。

輸入輸出格式

輸入格式:

?

  • Line 1: Two space-separated integers: N and M

  • Lines 2..M+1: Line i+1 contains the endpoints for path i: A_i and B_i

第一行:兩個整數N,M;

第2-M+1行:每行兩個整數,表示端點A_i 和 B_i 間有一條無向邊。

?

輸出格式:

?

  • Line 1: On a single line, print three space-separated integers: the index of the barn farthest from barn 1 (if there are multiple such barns, print the smallest such index), the smallest number of paths needed to reach this barn from barn 1, and the number of barns with this number of paths.

僅一行,三個整數,兩兩中間空格隔開。表示:距離第一個谷倉最遠的谷倉編號(如有多個則輸出編號最小的。),以及最遠的距離,和有幾個谷倉距離第一個谷倉那么遠。

?

輸入輸出樣例

輸入樣例#1:
6 7 
3 6 
4 3 
3 2 
1 3 
1 2 
2 4 
5 2 
輸出樣例#1:
4 2 3 

說明

The farm layout is as follows:

Barns 4, 5, and 6 are all a distance of 2 from barn 1. We choose barn 4 because it has the smallest index.

這里谷倉4,5,6距離1號谷倉都是2,但是4編號最小所以輸出4.因此最遠距離是2且有3個谷倉,依次輸出:2和3。?

感謝 wjcwinmt 的貢獻翻譯

?

最短路

堆優化dijkstra練習?

屠龍寶刀點擊就送

#include <algorithm>
#include <ctype.h>
#include <cstring>
#include <cstdio>
#include <queue>
#define N 100005
using namespace std;
struct node
{int x,y;bool operator<(node a)const{return y>a.y;}
};
struct dist
{int num,dis;bool operator<(dist b)const{if(dis==b.dis) return num<b.num;return dis>b.dis;}
}p[N];
priority_queue<node>q;
inline void read(int &x)
{x=0;bool f=0;register char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=1;for(; isdigit(ch);ch=getchar()) x=x*10+ch-'0';x=f?-x:x; 
}
bool vis[N];
int n,m,head[N],to[N],Next[N],cnt;
int main()
{freopen("hideseek.in","r",stdin);freopen("hideseek.out","w",stdout);read(n);read(m);for(int x,y;m--;){read(x);read(y);Next[++cnt]=head[x];to[cnt]=y;head[x]=cnt;Next[++cnt]=head[y];to[cnt]=x;head[y]=cnt;}for(int i=1;i<=n;i++) p[i].num=i,p[i].dis=0x7ffffff;p[1].dis=0;node a;a.x=1;a.y=p[1].dis;q.push(a);while(!q.empty()){node a=q.top();q.pop();if(vis[a.x]) continue;vis[a.x]=1;for(int i=head[a.x];i;i=Next[i]){int v=to[i];if(p[v].dis>p[a.x].dis+1){p[v].dis=p[a.x].dis+1;node b;b.x=v;b.y=p[v].dis;q.push(b); }}}sort(p+1,p+1+n);printf("%d %d",p[1].num,p[1].dis);int same=p[1].dis,ans=1;for(int i=2;i<=n;i++){if(p[i].dis==same) ans++;else break;}printf(" %d",ans);return 0;
}

?

轉載于:https://www.cnblogs.com/ruojisun/p/7354870.html

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/282740.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/282740.shtml
英文地址,請注明出處:http://en.pswp.cn/news/282740.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

使用ssh免密碼登錄Linux服務器

頻繁登錄Linux服務器時&#xff0c;使用ssh <username><host>的方式登錄&#xff0c;但是每次都需要輸入密碼是件很麻煩的事。我們還可以使用私鑰/公鑰對的方式在免密碼登錄服務器。首先需要在遠程服務器中安裝ssh-server服務&#xff0c;才可以使用ssh登錄。如果沒…

linux下tomcat開啟遠程調試

1.center下&#xff0c;在startup.sh文件首行中添加如下語句 declare -x CATALINA_OPTS"-server -Xdebug -Xnoagent -Djava.compilerNONE -Xrunjdwp:transportdt_socket,servery,suspendn,address8000"(不要換行&#xff0c;要在同一行)Ubuntu下&#xff0c;在catali…

.NET 7 RC1 發布

原文鏈接&#xff1a;https://devblogs.microsoft.com/dotnet/announcing-dotnet-7-rc-1/[1]原文作者&#xff1a;Jeremy Likness&#xff0c;Angelos Petropoulos&#xff0c;Jon Douglas翻譯&#xff1a;沙漠盡頭的狼(谷歌翻譯加持)今天我們宣布 .NET 7 候選版本 1。這是生產…

html 字符串最后加空格,html space空格符

htmlcss 代碼在網頁中如何插入打出空格字符實現方法**摘要瀏覽器總是會截短 HTML 頁面中的空格。HTML將所有空格字符&#xff0c;制表符&#xff0c;空格和回車符壓縮為一個字符。如果要縮進段落&#xff0c;則不能簡單地鍵入五個空格然后開始文本。 如果您在文本中寫 10 個空格…

.NET MAUI實戰 FilePicker

1.概要最近在遷移 GeneralUpdate.Tool的時候需要用到文件選擇&#xff0c;在MAUI中可以使用FilePicker進行選擇。ref1: https://gitee.com/Juster-zhu/GeneralUpdateref2:https://docs.microsoft.com/zh-cn/dotnet/maui/platform-integration/storage/file-picker?tabswindows…

SQL Server中,with as使用介紹

一&#xff0e;WITH AS的含義 WITH AS短語&#xff0c;也叫做子查詢部分&#xff08;subquery factoring&#xff09;&#xff0c;可以讓你做很多事情&#xff0c;定義一個SQL片斷&#xff0c;該SQL片斷會被整個SQL語句所用到。有的時候&#xff0c;是為了讓SQL語句的可讀…

從新手機到老股票 閑魚為何會淪為騙子與營銷的新平臺?

國內電商一直空缺一個有規模的綜合二手交易平臺。閑魚的出現&#xff0c;有一定程度上滿足了喜歡淘二手、喜歡“撿漏”的用戶需求。雖加入了擔保和第三方支付等環節&#xff0c;但這種隨機的二手交易行為不可避免地會出現上當、受騙的情況出現。本質上來說&#xff0c;閑魚仍然…

網上書店模板asp與html,一個簡單的網上書城的例子(三)_asp實例

buy.asp:顯示商品和用戶購物&#xff01;DbPath SERVER.MapPath("ShopBag.mdb")Set conn Server.CreateObject("ADODB.Connection")conn.open "driver{Microsoft Access Driver (*.mdb)};dbq" & DbPathCategoryIDRequest("CategoryID…

使用C#編寫一個.NET分析器(一)

譯者注這是在Datadog公司任職的Kevin Gosse大佬使用C#編寫.NET分析器的系列文章之一&#xff0c;在國內只有很少很少的人了解和研究.NET分析器&#xff0c;它常被用于APM&#xff08;應用性能診斷&#xff09;、IDE、診斷工具中&#xff0c;比如Datadog的APM&#xff0c;Visual…

內置數據類型

Java語言提供了八種基本類型。六種數字類型&#xff08;四個整數型&#xff0c;兩個浮點型&#xff09;&#xff0c;一種字符類型&#xff0c;還有一種布爾型。 byte&#xff1a; byte 數據類型是8位、有符號的&#xff0c;以二進制補碼表示的整數&#xff1b; 最小值是 -128&…

算法學習之循環結構程序設計

for循環 打印1,2,3&#xff0c;...&#xff0c;n每個占一行。 #include <conio.h> #include<stdio.h> int main(){int i,n;scanf("%d",&n);for(i1;i<n;i){printf("%d\n",i);}getch();return 0; } 分支結合循環&#xff0c;威力很強大 輸…

Linux常用命令 (分門別類)

一、系統安全: su: 用于切換當前用戶身份到其他用戶身份&#xff0c;變更時須輸入所要變更的用戶帳號與密碼 sudo: 用來以其他身份來執行命令&#xff0c;預設的身份為root lastlog: 用于顯示系統中所有用戶最近一次登錄信息 lastb: 用于顯示用戶錯誤的登錄列表&#x…

hibernate自定義校驗器使用(字段在in范圍之內)

2019獨角獸企業重金招聘Python工程師標準>>> 1.自定義注解類DigitsMustIn Constraint(validatedBy DigitsMustInValidator.class) //具體的實現 Target({java.lang.annotation.ElementType.METHOD,java.lang.annotation.ElementType.FIELD}) Retention(java.lang.a…

sql將html轉成excel,使用SQL*PLUS,構建完美excel或html輸出

通過SQL*PLUS我們可以構建友好的輸出&#xff0c;滿足多樣化用戶需求。本例通過簡單示例&#xff0c;介紹通過sql*plus輸出xls&#xff0c;html兩種格式文件.首先創建兩個腳本:1.main.sql用以設置環境&#xff0c;調用具體功能腳本2.功能腳本-get_tables.sql為實現具體功能之腳…

[cogs347]地震

COGS&#xff1a;地震&#xff08;平衡樹&#xff09; COGS上一道題。。。文件名是equake 還是又打了一遍板子。。。 加個lazy標記就行了。。。 注意查詢時先下傳標記&#xff08;lazy&#xff09; // It is made by XZZ #include<cstdio> #include<algorithm> #de…

第八課-第二講 08_02_bash腳本編程之七 case語句及腳本選項進階

第八課-第二講 08_02_bash腳本編程之七 case語句及腳本選項進階 一. 面向過程控制結構順序結構選擇結構循環結構選擇結構if語句 單分支&#xff0c;雙分支&#xff0c;多分支case 語句 case語句:選擇結構 case SWITCH invalue1)---此處的value是當做字符來比較的statement....…

html表單提交按鈕怎么居中,與表單框一致,居中提交按鈕_html_開發99編程知識庫...

我嘗試將提交按鈕與表單的一個條目對齊失敗。 我只是希望提交按鈕稍微定位到窗體框的右側和中心。 現在是右邊&#xff0c;但在盒子的底部。我試圖回答相似的查詢&#xff0c;對於提交按鈕( 浮點&#xff0c;margin 等等 )&#xff0c;但是我不能找到正確的選擇。我的HTML如下所…

一個簡單的WebService服務

現在&#xff0c;網上提供的免費的webservice服務的網站&#xff1a; http://www.webxml.com.cn/從擴展名上看&#xff0c;是 .net構建的網站。看看功能的實現效果&#xff1a;需求&#xff1a;我們要遠程調用手機號歸屬地的查詢&#xff1a;開發步驟&#xff1a; 1&#xff0e…

Linux中的vi和vim

一、vi與vim的概念和區別 概念: 它們都是多模式編輯器&#xff0c;不同的是vim 是vi的升級版本&#xff0c;它不僅兼容vi的所有指令&#xff0c;而且還有一些新的特性在里面。 vim優勢主要體現在一下幾方面: 1、多級撤消 我們知道在vi里&#xff0c;按 u只能撤消上次命令&a…

[工具分享]備份SSAS模型TMSL腳本元數據工具,多給自己一點后悔藥可吃。

筆者在2019年分享過自己寫的一個小工具&#xff0c;用于備份Sqlserver數據庫的元數據。近期在一個PowerBI項目中&#xff0c;發現很有必要也備份下SSAS分析模型的元數據&#xff0c;防止不小心服務器壞了或使用Tabular Editor連接數據庫方式開發過程中&#xff0c;不小心覆蓋了…