首页 > 代码库 > 【BZOJ1509】逃学的小孩
【BZOJ1509】逃学的小孩
1509: [NOI2003]逃学的小孩
Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 822 Solved: 409
[Submit][Status][Discuss]
Description
Input
第一行是两个整数N(3 ? N ? 200000)和M,分别表示居住点总数和街道总数。以下M行,每行给出一条街道的信息。第i+1行包含整数Ui、Vi、Ti(1?Ui, Vi ? N,1 ? Ti ? 1000000000),表示街道i连接居住点Ui和Vi,并且经过街道i需花费Ti分钟。街道信息不会重复给出。
Output
仅包含整数T,即最坏情况下Chris的父母需要花费T分钟才能找到Chris。
Sample Input
4 3
1 2 1
2 3 1
3 4 1
1 2 1
2 3 1
3 4 1
Sample Output
4
HINT
Source
Sol:
强烈安利:http://blog.sina.com.cn/s/blog_72aa02bd0100y5vt.html
/*To The End Of The Galaxy*/ #include<cstdio> #include<cstdlib> #include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<iomanip> #include<stack> #include<map> #include<time.h> #include<set> #include<cmath> #define debug(x) cerr<<#x<<"="<<x<<endl #define INF 0x7f7f7f7f #define llINF 0x7fffffffffffll #define P(x,y) (((x-1)*m)+y) using namespace std; typedef pair<int,int> pii; typedef long long ll; inline int init() { int now=0,ju=1;char c;bool flag=false; while(1) { c=getchar(); if(c==‘-‘)ju=-1; else if(c>=‘0‘&&c<=‘9‘) { now=now*10+c-‘0‘; flag=true; } else if(flag)return now*ju; } } inline long long llinit() { long long now=0,ju=1;char c;bool flag=false; while(1) { c=getchar(); if(c==‘-‘)ju=-1; else if(c>=‘0‘&&c<=‘9‘) { now=now*10+c-‘0‘; flag=true; } else if(flag)return now*ju; } } struct edge { int from,to,val,pre; }Edge[1000005]; int head[200005]; ll dis[200005]; bool vis[200005]; ll d[200005]; ll dist=0; int cnt=0,A,B; inline void addedge(int from,int to,int val) { ++cnt; Edge[cnt]=((edge){from,to,val,head[from]}); head[from]=cnt; } queue<int> q; int n,m; void bfs() { int now; q.push(1);dis[1]=0; while(!q.empty()) { now=q.front();q.pop(); if(vis[now])continue; vis[now]=1; for(int j=head[now];j;j=Edge[j].pre) { if(!vis[Edge[j].to]) { dis[Edge[j].to]=dis[now]+Edge[j].val; q.push(Edge[j].to); } } } ll nowmax=0; for(int i=1;i<=n;i++) { if(dis[i]>nowmax) { now=i;nowmax=dis[i]; } } A=now; memset(vis,0,sizeof(vis)); q.push(now);dis[now]=0; while(!q.empty()) { now=q.front();q.pop(); if(vis[now])continue; vis[now]=1; for(int j=head[now];j;j=Edge[j].pre) { if(!vis[Edge[j].to]) { dis[Edge[j].to]=dis[now]+Edge[j].val; q.push(Edge[j].to); } } } for(int i=1;i<=n;i++) { if(dis[i]>dist) { B=i; dist=dis[i]; } } now=B; memset(vis,0,sizeof(vis)); q.push(now);d[now]=0; while(!q.empty()) { now=q.front();q.pop(); if(vis[now])continue; vis[now]=1; for(int j=head[now];j;j=Edge[j].pre) { if(!vis[Edge[j].to]) { d[Edge[j].to]=d[now]+Edge[j].val; q.push(Edge[j].to); } } } } #ifdef unix #define LLD "%lld" #else #define LLD "%I64d" #endif int main() { ll ans=0; int a,b,c; n=init();m=init(); for(int i=1;i<=m;i++) { a=init();b=init();c=init(); addedge(a,b,c); addedge(b,a,c); } bfs(); for(int i=1;i<=n;i++) { if(i==A||i==B)continue; else { ans=max(ans,min(dis[i],d[i])+dist); } } printf(LLD"\n",ans); return 0; }
并没有写dp的做法
【BZOJ1509】逃学的小孩
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。