#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。
*/