gfoj 22的应急救援

86 阅读 0 评论 57 点赞

我是靠谱客的博主可爱外套，最近开发中收集的这篇文章主要介绍gfoj 22的应急救援，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：http://www.gdfzoj.com/oj/contest/277/problems/2

bilibili拜年祭上，小妹妹被邪♂恶的组织带♂走的事情，引发了22和33的关注。

小妹妹被带到了从22和33所在地区出发最危♂险的地区。

22需要尽可能快地赶到小妹妹被带♂去的地点，来保护 ' knows nothing about *♂* ' 的小妹妹。

总路程的危险值是叠加的，也就是说22每经过一条路，她的路程的危险值就要加上该道路的危险值。

Input

第一行有 n , m , s 三个正整数 ( 1<n<=100000 , m<=200000 , 0<s<=n ) 表示邪♂恶组织地盘数和道路数以及22的出发地

接下来的 m 行，每行有3个正整数 a , b , c ( a , b<=n , 0<c<=100000 )

a，b 表示道路所连通的地区，c 表示该道路危险值，越大代表越危险

由于邪♂恶组织道路比较邪♂恶，所以只能保证道路可以使任意两城市互达（道路是无向的）

Output

输出一个正整数，表示22到达小妹妹所在区域所经历的总危险值的最小值

Sample Input

2 1 1

1 2 233

Sample Output

233

史上最坑样例，没有之一。。。

题目中的答案是求最大值。。。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
struct node
{
int u,v,w,next;
};
const int maxS=200000;
node edge[maxS*2+5];
int tmp=0,n,m,s;
int head[maxS+5],vis[maxS+5];
long long dis[maxS+5];
queue <int> q;
void addedge(int x,int y,int z)
{
tmp++;
edge[tmp].u=x;
edge[tmp].v=y;
edge[tmp].w=z;
edge[tmp].next=head[x];
head[x]=tmp;
}
void spfa()
{
int i,x,y;
long long max1=0;
q.push(s);	vis[s]=1;	dis[s]=0;
while (!q.empty())
{
x=q.front();	q.pop();	vis[x]=0;
for (i=head[x];i;i=edge[i].next)
{
y=edge[i].v;
if (dis[x]+edge[i].w<dis[y])
{
dis[y]=dis[x]+edge[i].w;
if (vis[y]==1)
continue;
q.push(y);
vis[y]=1;
}
}
}
for (i=1;i<=n;i++)
max1=max(max1,dis[i]);
printf("%lldn",max1);
}
int main()
{
int i,x,y,z;
freopen("a.txt","r",stdin);
scanf("%d%d%d",&n,&m,&s);
for (i=0;i<m;i++)
{
scanf("%d%d%d",&x,&y,&z);
addedge(x,y,z);
addedge(y,x,z);
}
memset(vis,0,sizeof(vis));
memset(dis,0x3f,sizeof(dis));
spfa();
return 0;
}