输入输出外挂

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;
}