为什么只有88分
查看原帖
为什么只有88分
995962
封禁用户楼主2023/5/27 11:43
#include<bits/stdc++.h>
#define INF 2147483647
#define MAXN 100010
#define MAXM 200010
using namespace std;
struct edge{
	int v,w,nxt;
}e[MAXM];
struct Node{
	int id,dis;
	bool operator < (const Node &rhs) const
	{
		return dis>rhs.dis;
	}
}a[MAXN];
int n,m,l,cnt;
int path[MAXN],pos[MAXN];
int head[MAXN],st[MAXN];
int f[MAXN],g[MAXN];
int dist[MAXN],stk[MAXN],p;
bool used[MAXN],vis[MAXN];
void add (int u,int v,int w)
{
	e[++cnt].v=v;
	e[cnt].w=w;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
priority_queue<Node>heap;
queue<int>q;
void spfa (int s,int w,int id,int lct)
{
	memset (vis,0,sizeof (vis));
	q.push (s);used[s]=1;
	dist[s]=w;p=0;
	while (!q.empty ())
	{
		int u=q.front ();
		q.pop ();used[u]=0;
		for (int i=head[u];i!=0;i=e[i].nxt)
			if (i!=id)
			{
				if (pos[e[i].v]>lct)
				{
					if (!vis[pos[e[i].v]])
					{
						vis[pos[e[i].v]]=1;
						stk[++p]=e[i].v;
						a[e[i].v].id=pos[e[i].v];
						a[e[i].v].dis=dist[u]+e[i].w+g[pos[e[i].v]];
					}
					else
						a[e[i].v].dis=min (a[e[i].v].dis,dist[u]+e[i].w+g[pos[e[i].v]]);
				}
				else if (dist[e[i].v]>dist[u]+e[i].w)
				{
					dist[e[i].v]=dist[u]+e[i].w;
					if (!used[e[i].v])
					{
						q.push (e[i].v);
						used[e[i].v]=1;
					}
				}
			}
	}
	while (p) heap.push (a[stk[p--]]);
}
int main()
{
	scanf ("%d%d%d",&n,&m,&l);
	for (int i=1;i<=m;i++)
	{
		int u,v,w;
		scanf ("%d%d%d",&u,&v,&w);
		add (u,v,w);
	}
	st[1]=pos[1]=1;
	for (int i=1;i<=l;i++)
	{
		scanf ("%d",&path[i]);
		pos[e[path[i]].v]=i+1;
		st[i+1]=e[path[i]].v;
	}
	for (int i=2;i<=l;i++)
		f[i]=f[i-1]+e[path[i-1]].w;
	for (int i=l;i>=1;i--)
		g[i]=g[i+1]+e[path[i]].w;
	for (int i=1;i<=n;i++)
		dist[i]=INF;
	for (int i=1;i<=l;i++)
	{
		spfa (st[i],f[i],path[i],i);
		while (!heap.empty ()&&heap.top ().id<=i)
		{
			vis[heap.top ().id]=0;
			heap.pop ();
		}
		if (heap.empty ()) printf ("-1\n");
		else printf ("%d\n",heap.top ().dis);
	}
	return 0;
}
2023/5/27 11:43
加载中...