输入输出外挂
void read(int &x)
{
int f=1;x=0;char s=getchar();
while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
while(s<='9'&&s>='0'){x=x*10+s-'0';s=getchar();}
x=f*x;
}//快读(有的时候可以神奇的卡入一些神奇的TLE)
套一道题
问题描述
蒜头君准备去参加骑车比赛,比赛在 n 个城市间进行,编号从 1 到 n。选手们都从城市 1 出发,终点在城市 n。
已知城市间有 m 条道路,每条道路连接两个城市,注意道路是双向的。现在蒜头君知道了他经过每条道路需要花费的时间,他想请你帮他计算一下,他这次比赛最少需要花多少时间完成。
输入格式
第一行输入两个整数n,m(1≤n≤1,000,1≤m≤5,000),分别代表城市个数和道路总数。接下来输入 m 行,每行输入三个数字 a,b,c(1≤a,b≤n,1≤c≤200),分别代表道路的起点和道路的终点,以及蒜头君骑车通过这条道路需要花费的时间。保证输入的图是连通的。
输出格式
输出一行,输出一个整数,输出蒜头君完成比赛需要的最少时间。
样例输入
5 6
1 2 2
2 3 3
2 5 5
3 4 2
3 5 1
4 5 1
样例输出
6
一道最短路模板
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<queue>//优先队列在这个库里
using namespace std;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;//定义一个小根堆(优先队列
int n,m,num,s;
int he[100010],d[100010],inq[100010];
//d数组表示点i和起点之间的距离,inq记录点i是否已确定,he是前向星存边~
void read(int &x)
{
int f=1;x=0;char s=getchar();
while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
while(s<='9'&&s>='0'){x=x*10+s-'0';s=getchar();}
x=f*x;
}//快读
struct node
{
int nxt;
int to;
int dis;
}edg[200020];//前向星
void add(int a,int b,int c)
{
edg[++num].to=b;
edg[num].dis=c;
edg[num].nxt=he[a];
he[a]=num;
}//存边!
void dst(int s)
{
memset(d,0x3f3f3f3f,sizeof(d));//初始化
memset(inq,0,sizeof(inq));
q.push(make_pair(0,s));//起点入队(堆)了
d[s]=0;//自己到自己,距离0
while(!q.empty())//队(堆)不是空的,此时距离起点最小的 点在队首(堆顶)
{
int x=q.top().second;//x:找到该点
q.pop();//出队(堆),去履行更新其他点的光荣义务
if(inq[x])continue;//如果这是一个已经确定过的点 ,拜拜
inq[x]=1;
int t=he[x];
while(t)//遍历一遍这个点连向的点,更新最短路
{
if(d[edg[t].to]>d[x]+edg[t].dis&&!inq[edg[t].to])
{
d[edg[t].to]=d[x]+edg[t].dis;
q.push(make_pair(d[edg[t].to],edg[t].to));//被更新了,进去
}
t=edg[t].nxt;
}
}
}
int main()
{
int xx,yy,ww;
read(n);read(m);
for(int i=1;i<=m;i++)
{
read(xx);read(yy);read(ww);
add(xx,yy,ww);//无向图
add(yy,xx,ww);
}
dst(1);
cout<<d[n];
return 0;
}
One comment