首页 > 代码库 > P2299 Mzc和体委的争夺战
P2299 Mzc和体委的争夺战
题目背景
ｍｚｃ与ｄｊｎ第四弹。
题目描述
ｍｚｃ家很有钱（开玩笑），他家有ｎ个男家丁（做过前三弹的都知道）。但如此之多的男家丁吸引来了我们的体委（矮胖小伙），他要来与ｍｚｃ争夺男家丁。
ｍｚｃ很生气，决定与其决斗，但ｃａｔ的体力确实有些不稳定，所以他需要你来帮他计算一下最短需要的时间。
输入输出格式
输入格式：
第一行有两个数ｎ，ｍ，ｎ表示有ｎ个停留站，ｍ表示共有ｍ条路。
之后ｍ行，每行三个数ａ［ｉ］，ｂ［ｉ］，ｃ［ｉ］，表示第ａ［ｉ］个停留站到第ｂ［ｉ］个停留站需要ｃ［ｉ］的时间。（无向）
输出格式：
一行，输出１到ｍ最短时间。
输入输出样例
输入样例#1：
5 81 2 32 3 43 4 54 5 61 3 42 4 72 5 81 5 100
输出样例#1：
11
说明
ｎ＜＝２５００
由于mzc大大十分着急，所以他只能等待1S。
spfa模板，只是要建双向边
#include<bits/stdc++.h>#define maxn 3125000#define INF 2147483647using namespace std;int n,m,x,y,w,s,dis[maxn],head[maxn],num;struct Edge{ int to,dis,next;}edge[maxn];inline void add_edge(int from,int to,int dis){ num++; edge[num].to=to; edge[num].dis=dis; edge[num].next=head[from]; head[from]=num;}inline void spfa(int now){ queue<int>que; bool if_in[maxn]; for(int i=1;i<=n;i++) dis[i]=INF,if_in[i]=false; dis[now]=0; if_in[now]=true; que.push(now); while(!que.empty()) { int cur=que.front(); que.pop(); for(int i=head[cur];i;i=edge[i].next) { if(edge[i].dis+dis[cur]<dis[edge[i].to]) { dis[edge[i].to]=dis[cur]+edge[i].dis; if(!if_in[edge[i].to]) { if_in[edge[i].to]=true; que.push(edge[i].to); } } } if_in[cur]=false; }}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&w); add_edge(x,y,w); add_edge(y,x,w); } spfa(1); printf("%d ",dis[n]); return 0;}
P2299 Mzc和体委的争夺战
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。