#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<set>
#include<queue>
#include<vector>

using namespace std;
const int inf=0x7f7f7f7f;

const int NUM_NODE=100010;

struct edge{ // 边的数据结构
	int to;int weight;
	edge(int t,int w):to(t),weight(w){}
};

vector<edge> e[NUM_NODE];
int dist[NUM_NODE];

void dijkstra(int s){
	memset(dist,inf,sizeof(dist)); // 距离初始化为inf
	bool visited[NUM_NODE]; // 是否确定最短路
	memset(visited,0,sizeof(visited));
	dist[s]=0;visited[s]=true; // 初始化源点状态

	set<pair<int,int> > st; // 维护unvisited顶点的距离
	int cur=s; // 现在所处的点
	while(1){
		for(edge i:e[cur]){
			if(!visited[i.to]&&dist[i.to]>dist[cur]+i.weight){
				// 如果未确定最短路，且经过我会让你更近一些
				if(dist[i.to]!=inf) // 如果旧的距离信息被记录了
					st.erase(st.find(pair<int,int>(dist[i.to],i.to))); // 擦掉旧的距离信息
				dist[i.to]=dist[cur]+i.weight; // 更新距离
				st.insert(pair<int,int>(dist[i.to],i.to)); // 加入新的距离信息
			}
		}
		if(st.empty())return; // 没有能到达、且最短路不确定的顶点了
		cur=st.begin()->second;visited[cur]=true; // 取出距离最短顶点，它的最短路确定了
		st.erase(st.begin()); // 不再考虑它
	}
}

int main(){
	ios::sync_with_stdio(false);

	return 0;
}
/*

dijkstra算法用来求单源最短路，不能处理负权边，复杂度为o(nlogn)。

我们用STL的set维护unvisited顶点的距离，用logn的时间找到距离最短顶点。

visited：是否确定最短路。

1. 我们站在源点（cur=源点），设源点为visited。
2. 对每一个与cur邻接的、visited=false的点，如果经过源点到达它路径更短，更新路径。
3. 取出目前visited=false且距离最短的顶点，将它设为新cur，并visited=true。

*/