牛客国庆集训派对Day3I.Metropolis(Dijkstra变型)

题意:求一个N个点无向图中,其中p个关键点间的最短距离.
分析:比较特殊的最短路,方式类似于多源BFS,将所有关键点装入优先队列,状态中需要包含其源点的id.对每条边都要遍历,对每个节点,需要记录其确定最短的源头以及其最短距离.当一个访问状态到达了与自己源头状态不同的点,则说明两个关键点相遇,每次相遇时,更新两个源头的最短距离.

#include
using namespace std;
typedef long long LL;
const int MAXN &＃61; 2e5&＃43;5;
const LL INF &＃61; (1LL)<<60;
struct Edge{int v,next;LL w;
}E[MAXN<<2];
int head[MAXN],tot;
int vis[MAXN];
LL d[MAXN],link[MAXN];
vector st;
int N,M,k;void init()
{st.clear();memset(head,-1,sizeof(head));tot &＃61; 0;
}void AddEdge(int u,int v,int w){E[tot] &＃61; (Edge){v,head[u],w};head[u] &＃61; tot&＃43;&＃43;;
}struct HeapNode{int u,sta;LL val;bool operator <(const HeapNode & rhs) const{return val > rhs.val;}
};
void Dijkstra()
{for(int i&＃61;0;i<&＃61;N;&＃43;&＃43;i) d[i] &＃61; INF, vis[i] &＃61; 0;priority_queue Q;for(int i&＃61;0,sz &＃61; st.size();i}int main()
{#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifscanf("%d %d %d",&N, &M, &k);init();int u,v;LL w;while(k--){scanf("%d",&u);st.push_back(u);}while(M--){scanf("%d %d %lld",&u,&v,&w);AddEdge(u,v,w);AddEdge(v,u,w);}Dijkstra();for(int i&＃61;0,sz &＃61; st.size();i}