自动搬运

查看原文

来自洛谷，原作者为

	公主殿下MIKU **

搬运于2025-08-24 21:40:25，当前版本为作者最后更新于2018-12-08 16:07:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

裸的最短路模板，数据范围小，完全可以直接在每次询问的时候跑一遍最短路就行，如果担心时间的话，可以用堆优化的dijkstra,完全可以过，堆可以手打，但作为stl党， 我们可是有黑科技的。优先队列相当于一个大根堆，你可以使用stl的pair使他成为小根堆，也可以通过运算符装载将其重载为小根堆。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
struct node{//小根堆重载
    int now,x;//now代表点的位置，x代表距离
    bool operator <(const node &tmp) const
    {
        return x>=tmp.x;
    }
}cur;
int head[110],to[10010],nxt[10010],v[10010],num,dis[10010],e,n,m,x,y,k;
bool vis[110];
const int inf=2147483647; 
void add(int x,int y,int z)//前向星建图，因为是双向边，所以存两条边
{
    to[++num]=y;
    v[num]=z;
    nxt[num]=head[x];
    head[x]=num;
    to[++num]=x;
    v[num]=z;
    nxt[num]=head[y];
    head[y]=num;
}
void dij(int s)
{
    priority_queue<node>q;
    fill(dis+1,dis+n+1,inf);//初始化，一定要初始化，不然它会与上次查询有冲突。
    fill(vis+1,vis+n+1,0);
    dis[s]=0;
    q.push((node){
        s,dis[s]
    });
    while(!q.empty())
    {
        cur=q.top();
        q.pop();
        if(vis[cur.now]) continue;
        vis[cur.now]=1;
        for(int i=head[cur.now];i;i=nxt[i])
        {
            if(dis[to[i]]>dis[cur.now]+v[i])//路径压缩
            {
                dis[to[i]]=dis[cur.now]+v[i];
                q.push((node){
                    to[i],dis[to[i]]
                });
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&k);
        if(k==0)
        {
            scanf("%d%d",&x,&y);
            dij(x);//遍历最短路
            printf("%d\n",dis[y]==inf?-1:dis[y]);
        }
        else 
        {
            scanf("%d%d%d",&x,&y,&e);
            add(x,y,e);//加边
        }
    }
    return 0;
}	

管理大大求过。