---

思路分析

最短路模板题，有两个注意点

1. 一次，多组数据，注意对数组的清空。
2. 无向图，建图的时候注意要add正反两次。

每次都要初始化

void init()
{
	memset(h,-1,sizeof h);
	memset(vis,0,sizeof vis);
	memset(dis,0x3f,sizeof dis);
	idx = 0;
}

spfa

起始点为1，终点为n。

		auto spfa = [&]()->void
		{
			queue<int> q;
			q.push(1);
			vis[1] = 1;
			dis[1] = 0;
			while(q.size())
			{
				auto t = q.front();
				q.pop();
				vis[t] = 0;
				for(int i = h[t];~i;i=ne[i])
				{
					int j = e[i];
					if(dis[j] > dis[t] + w[i])
					{
						dis[j] = dis[t] + w[i];
						if(!vis[j])
						{
							q.push(j);
							vis[j] = 1;
						}
					}
				}
			}
		};

时间复杂度O(nm)

完整AC代码：

#include <bits/stdc++.h>


#define fi first
#define endl '\n'
#define se second
#define pp pop_back
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define all(a) begin(a),end(a)
#define lp(i,j,k) for(int i=int(j);i<=int(k);i++)
#define rlp(i,j,k) for(int i=int(j);i>=int(k);i--...