タイトル：リンク
方法：SPFA
解析:
この問題は深く捜すのは死んだので,私になぜか聞かないでください。
深搜过程大概会RE 8个点--!
複雑さはO(nm)に似ていますか?
実は全体的にSPFAですが、ここではいくつかの変更が必要です。
このトラはDPトラで、彼は毎回あなたの最善の案を占めています。
したがって、最適なシナリオと最適なシナリオを更新するには、セカンダリ・シナリオしか使用できません。
これがSPFAの道です。
しかし、この道は足りない。
一つの点で息子が一人しかいないときを考えてみましょう。
彼は一周してから初めて息子に答えを更新させるかもしれない。
この時は最短で短絡していない。
しかし、息子の情報を更新するに違いありません。
この時、息子はまたこの点を更新しに来ます。
では、私たちのシミュレーションに従えば、息子は短距離と最短距離を更新します。
しかし、明らかに、この点は短距離ではない。
だから、この点に短距離を更新すると、この点がさらに上に進むと答えに影響します。
だからこのような状況は避けなければならない。
具体的にはどうやって避けますか?
前回誰に更新されたかを記録し、次回が同じであれば短距離は更新されません。
複雑度はSPFA複雑度であり、許容できる。
コード:
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 100100
#define M 1000010
using namespace std;
int n,m,k,cnt;
int vip[N];
int head[N];
int v[N];
int val[N];
int dis[N];
int sec_dis[N];
int pre[N];
struct node
{
int from,to,val,next;
}edge[M<<1];
void init()
{
memset(dis,0x3f,sizeof(dis));
memset(sec_dis,0x3f,sizeof(sec_dis));
memset(head,-1,sizeof(head));
cnt=1;
}
void edgeadd(int from,int to,int val)
{
edge[cnt].from=from,edge[cnt].to=to,edge[cnt].val=val;
edge[cnt].next=head[from];
head[from]=cnt++;
}
void bfs()
{
queue<int>q;
for(int i=1;i<=k;i++)
{
int x;
scanf("%d",&x);x++;
dis[x]=sec_dis[x]=0;
q.push(x);
v[x]=1;
}
while(!q.empty())
{
int u=q.front();
q.pop();
v[u]=0;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int to=edge[i].to;
if(sec_dis[u]+edge[i].val<=dis[to])
{
if(pre[to]!=u)
sec_dis[to]=dis[to];
dis[to]=sec_dis[u]+edge[i].val;
pre[to]=u;
if(!v[to])
{
q.push(to);
v[to]=1;
}
}else if(sec_dis[u]+edge[i].val<sec_dis[to])
{
sec_dis[to]=sec_dis[u]+edge[i].val;
if(!v[to])
{
q.push(to);
v[to]=1;
}
}
}
}
}
int main()
{
init();
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
x++,y++;
edgeadd(x,y,z);
edgeadd(y,x,z);
}
bfs();
printf("%d
",sec_dis[1]);
}