G. Silver Cow Party
Time Limit:2000ms
Case Time Limit:2000ms
Memory Limit:65536KB
Font Size:
+
-
One cow from each ofNfarms (1 ≤N≤ 1000) conveniently numbered 1..Nis
going to attend the big cow party to be held at farm #X(1 ≤X≤N).
A total ofM(1 ≤M≤ 100,000) unidirectional (one-way roads connects pairs of farms; roadirequiresTi(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
iwith
three space-separated integers:
Ai,
Bi,
and
Ti. The described road runs from farm
Aito
farm
Bi, requiring
Titime
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
这道题其实是一道最短路的变形。在建图的时候正反各建立一次,然后用spfa求得相应的距离。
这里要注意一下,以后建图的时候尽可能用邻接表来建立。(可以用数组,可以用vector、list)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#define INF 10000000
using namespace std;
int n,m,x,dist_v1[1010]= {0},dist_v2[1010]= {0};
struct node
{
int x,d;
};
vector<node> v1[1010];
vector<node> v2[1010];
void spfa_v1(int x)
{
int i,j,visit[1010]= {0},t;
queue<int> q;
for (i=1; i<=n; i++)
dist_v1[i]=INF;
dist_v1[x]=0;
visit[x]=1;
q.push(x);
int s,l;
while(!q.empty())
{
t=q.front();
q.pop();
visit[t]=0;
for (i=0; i<v1[t].size(); i++)
{
s=v1[t][i].x;
l=v1[t][i].d;
if (dist_v1[s]>dist_v1[t]+l)
{
dist_v1[s]=dist_v1[t]+l;
if (!visit[s])
{
visit[s]=1;
q.push(s);
}
}
}
}
}
void spfa_v2(int x)
{
int i,j,visit[1010]= {0},t;
queue<int> q;
for (i=1; i<=n; i++)
dist_v2[i]=INF;
dist_v2[x]=0;
visit[x]=1;
q.push(x);
int s,l;
while(!q.empty())
{
t=q.front();
q.pop();
visit[t]=0;
for (i=0; i<v2[t].size(); i++)
{
s=v2[t][i].x;
l=v2[t][i].d;
if (dist_v2[s]>dist_v2[t]+l)
{
dist_v2[s]=dist_v2[t]+l;
if (!visit[s])
{
visit[s]=1;
q.push(s);
}
}
}
}
}
int main ()
{
int i,j;
int a,b,t;
scanf("%d%d%d",&n,&m,&x);
node e;
while(m--)
{
scanf("%d%d%d",&a,&b,&t);
e.x=b;
e.d=t;
v1[a].push_back(e);
e.x=a;
v2[b].push_back(e);
}
spfa_v1(x);
spfa_v2(x);
int max=0,s1,s2;
for (i=1; i<=n; i++)
{
if (max<dist_v1[i]+dist_v2[i])
max=dist_v1[i]+dist_v2[i];
}
cout<<max<<endl;
return 0;
}
分享到:
相关推荐
David Silver 大神是 AlphaGo 的最主要研发人员,师从强化学习之父Richard Sutton,公开课讲解的内容十分生动,结合课程课件配合视频学习效率更高。课程如下: Part I: Elementary Reinforcement Learning 1 ...
PS 滤镜插件,Silver.Efex.Pro.v1.0。
Silver Efex Pro 2滤镜是可以将彩色图片处理成各种黑白颜色图片的滤镜。 本压缩包无密码。 安装步骤: 1. 安装Silver Efex Pro 2滤镜. 2.从Photoshop打开Silver Efex Pro 2滤镜. 注册的时候选择电话激活,用Silver ...
支持WPF ComboBox多选的封装dll,例子地址https://blog.csdn.net/m0_37137902/article/details/107090955
简单分页的文件(升级到的6.0版本)
资源来自pypi官网。 资源全名:silver-0.3.3.tar.gz
David Silver强化学习的ppt和一些其他资料,中文字幕视频链接:https://www.bilibili.com/video/av32149008/?p=2
No silver bullet.pdf
Panuon.UI.Silver Panuon.UI optimized version. A beautiful wpf ui library using templates & attached properties. Panuon.UI的优化版本。一个漂亮的、使用样式与附加属性的WPF UI控件库。 Email : QQ Group : ...
David Silver强化学习PPT,一共10节课,可以配合B站上的视频使用,也可以结合Sutton强化学习第二版的书籍使用,PPT中里面的重点可以很快的抓住问题的核心,同时能够更加清晰的理解概念!
python库。 资源全名:silver_spectacle-0.1.1.tar.gz
目录(Contents) 二十周年纪念版序言(PREFACE TO THE 20TH ANNIVERSARY EDITION)......................I 第一版序言(PREFACE TO THE FIRST EDITION)...........................................................
资源分类:Python库 所属语言:Python 资源全名:silver-payu-0.3.5.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
12. boston-gpu.earth ............................................................................................................15 13. bumpmap.earth .....................................................
043 A Silver Shilling.doc
- 电话日志.....................................................................................................................................38 产品测试.................................................
silver-ye.github.io
强化学习(Reinforcement Learning,RL)灵感来源于心理学中的行为主义理论,即有机体如何在环境给予的奖励或惩罚的刺激下,逐步形成对刺激的预期,产生能获得最大利益的习惯性行为。
Telerik RadControls Silverlight 正式版,...Telerik.Windows.Themes.Office_Silver.dll Telerik.Windows.Themes.Summer.dll Telerik.Windows.Themes.Vista.dll http://www.telerik.com/products/silverlight.aspx
A TensorFlow implementation of the models described in Andor et al. (2016).