#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const long long int inf=1e18;
struct cell
{
long long int from,to,st;
bool operator<(const cell&a)const
{
return st>a.st;
}
};
struct query
{
long long int ind,st;
};
bool cmp(query a1,query a2)
{
return a1.st<a2.st;
}
int n,m,t,k,b[2005];
cell a[2005];
query c[2005];
vector<cell>v[2005];
long long int used1[6005][2005],par1[6005][2005],used2[6005][2005],par2[6005][2005],ind[2005][2005],lamp[2005];
void dijkstra(int beg,int from,int ind)
{
cell w,nb;
w.from=from;
w.to=beg;
w.st=0;
priority_queue<cell>q;
q.push(w);
memset(lamp,0,sizeof(lamp));
long long int st;
while(q.size())
{
w=q.top();
q.pop();
//cout<<w.from<<" "<<w.to<<" "<<used1[ind][w.to]<<" "<<used2[ind][w.to]<<endl;
if(lamp[w.to]==2)continue;
lamp[w.to]++;
for(int i=0;i<v[w.to].size();i++)
{
nb=v[w.to][i];
if(lamp[w.to]==1)
{
st=used1[ind][w.to]+v[w.to][i].st;
if(nb.to==w.from)continue;
}
else
{
st=used2[ind][w.to]+v[w.to][i].st;
if(nb.to==w.from)continue;
}
//cout<<st<<" "<<nb.to<<endl;
nb.st=st;
if(used1[ind][nb.to]>st||!used1[ind][nb.to])
{
//cout<<nb.to<<" !1"<<endl;
q.push(nb);
used2[ind][nb.to]=used1[ind][nb.to];
par2[ind][nb.to]=par1[ind][nb.to];
used1[ind][nb.to]=st;
par1[ind][nb.to]=w.to;
}
else if(used2[ind][nb.to]>st||!used2[ind][nb.to])
{
//cout<<nb.to<<" !2"<<endl;
q.push(nb);
used2[ind][nb.to]=st;
par2[ind][nb.to]=w.to;
}
}
}
}
void prec()
{
int br=0;
for(int i=1;i<=n;i++)
{
br++;
ind[i][0]=br;
dijkstra(i,0,br);
}
for(int i=1;i<=m;i++)
{
br++;
ind[a[i].to][a[i].from]=br;
dijkstra(a[i].to,a[i].from,br);
br++;
ind[a[i].from][a[i].to]=br;
dijkstra(a[i].from,a[i].to,br);
}
/*
for(int i=1;i<=n;i++)
{
for(int j=0;j<=n;j++)
{
br=ind[i][j];
cout<<i<<" "<<j<<" | ";
for(int z=1;z<=n;z++)
{
cout<<used1[br][z]<<" ";
}
cout<<endl;
}
}
*/
}
query mi[10];
void resh()
{
long long int ot1=0,ot2=0,p1=0,p2=0,in;
for(int i=1;i<k;i++)
{
if(i==1)
{
in=ind[b[i]][0];
ot1=used1[in][b[i+1]];
ot2=used2[in][b[i+1]];
p1=par1[in][b[i+1]];
p2=par2[in][b[i+1]];
//cout<<ot1<<" "<<ot2<<" "<<p1<<" "<<p2<<endl;
continue;
}
in=ind[b[i]][p1];
if(used1[in][b[i+1]]==0&&(!p2||used1[ind[b[i]][p2]][b[i+1]]==0))
{
cout<<-1<<endl;
return;
}
mi[1].st=ot1+used1[in][b[i+1]];
mi[1].ind=par1[in][b[i+1]];
mi[2].st=ot1+used2[in][b[i+1]];
mi[2].ind=par2[in][b[i+1]];
in=ind[b[i]][p2];
if(!p2)in=ind[n+1][0];
mi[3].st=ot2+used1[in][b[i+1]];
mi[3].ind=par1[in][b[i+1]];
mi[4].st=ot2+used2[in][b[i+1]];
mi[4].ind=par2[in][b[i+1]];
if(mi[1].st==ot1)mi[1].st=inf;
if(mi[2].st==ot1)mi[2].st=inf;
if(mi[3].st==ot2||!ot2)mi[3].st=inf;
if(mi[4].st==ot2||!ot2)mi[4].st=inf;
sort(mi+1,mi+5,cmp);
ot1=mi[1].st;
p1=mi[1].ind;
if(mi[2].st!=inf&&mi[2].ind!=p1)
{
ot2=mi[2].st;
p2=mi[2].ind;
}
else if(mi[3].st!=inf)
{
ot2=mi[3].st;
p2=mi[3].ind;
}
//cout<<ot1<<" "<<ot2<<" "<<p1<<" "<<p2<<endl;
}
cout<<ot1<<endl;
}
void read()
{
cin>>n>>m>>t>>k;
for(int i=1;i<=m;i++)
{
cin>>a[i].from>>a[i].to>>a[i].st;
v[a[i].from].push_back(a[i]);
swap(a[i].from,a[i].to);
v[a[i].from].push_back(a[i]);
}
prec();
for(int i=1;i<=k;i++)
{
cin>>b[i];
}
for(int i=1;i<=t;i++)
{
cin>>c[i].ind>>c[i].st;
b[c[i].ind]=c[i].st;
resh();
}
}
int main()
{
speed();
read();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |