暑假集训的休息日到了,本想在学校自习的babilong在ly和sun_of_Ice的蛊惑下,被拉去了MY的电影院玩游戏。MY共有n个区域,包括学校,电影院和n-2个其他区域,其他区域中都是休息站,休息站中没有学校和电影院。并且在MY有m条道路,每条道路连接a,b两个区域且通过此条道路需要付出c的价格(双向道路)。他们决定乘坐鸽鸽专车从学校前往电影院,因为这样虽然咕咕咕咕但经济实惠。优惠政策有2条如下所示:
1.MY的每条道路都可以半价优惠。
2.可以选择给定k条道路中的任意一条道路免费,其他道路原价收费。
因为xx的原因,他们只能选择一条优惠政策,当然也可以不选择。
Input
第一行包括4个整数
n
,
m
,
s
,
e
(
2
≤
n
≤
1000
,
1
≤
m
≤
10000
,
1
≤
s
,
e
≤
n
)
,分别表示有
n
个区域,
m
条道路,学校所在的区域s,电影院所在的区域e。
接下来
m
行每行3个整数
a
,
b
,
c
(
1
≤
a
,
b
≤
n
,
1
≤
c
≤
1000
)
表示
m
条道路的信息。
接下来一个整数
k
(
0
≤
k
≤
1000
)
,表示有
k
条道路可选择其中的一条免费。
最后
k
行,每行一个整数
x
(
1
≤
x
≤
m
)
表示可以选择第
x
条道路免费。
Output
第一行输出从学校到电影院的最小花费,若不能到达输出-1。
Sample Input
Raw
5 5 1 5
1 2 2
2 3 2
2 4 2
3 5 100
4 5 2
1
4
Sample Output
Raw
3
这个题首先用dij求出半价最短路,然后在让能免费的路全部遍历一次,每次记录,计算,再恢复,求出最小。第一次我都是用for循环直接暴力的,但超时了。我一直认为是在求免费路时没有优化,后来想了一下,每一次都要进行dij,我们就可以优化dij,所以用优先队列优化dij就就可以了。
代码:
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#define me(x,b) memset(x,b,sizeof(x))
#define lowbit(x) x&(-x)
#include<queue>
using namespace std;
typedef long long ll;
const int maxn=1e4+5;
const int maxn1=1e6;
int vis[1005];
int d[1005];
int t[1005];
int head[maxn];
int n,m,x,y;
struct node
{
int t,next,val;
}e[maxn<<2];
void add(int x,int y,int val, int k)
{
e[k].t=y;
e[k].val=val;
e[k].next=head[x];
head[x]=k;
}
int dij(int a)
{
me(vis,0);
for(int i=0;i<=n;i++)
d[i]=maxn1;
d[a]=0;
queue<int>q;
q.push(a);
while(!q.empty())
{
int x=q.front();
q.pop();
vis[x]=0;
for(int i=head[x];~i;i=e[i].next)
{
int t=e[i].t;
int val=e[i].val;
if(d[t]>d[x]+val)
{
d[t]=d[x]+val;
if(vis[t]==0)
{
q.push(t);
vis[t]=1;
}
}
}
}
return d[y];
}
int main()
{
me(head,-1);
scanf("%d %d %d %d",&n,&m,&x,&y);
int a,b,v;
int c=1;
while(m--)
{
scanf("%d %d %d",&a,&b,&v);
add(a,b,v,c++);
add(b,a,v,c++);
}
int k;
scanf("%d",&k);
for(int i=1;i<=k;i++)
scanf("%d",&t[i]);
int s=dij(x);
if(s==maxn1)
{
printf("-1\n");
}
else
{
s=s/2;
int x1;
for(int i=1;i<=k;i++)
{
x1=e[t[i]*2-1].val;
e[t[i]*2-1].val=0;
e[t[i]*2].val=0;
int s1=dij(x);
s=min(s1,s);
e[t[i]*2-1].val=x1;
e[t[i]*2].val=x1;
}
printf("%d\n",s);
}
return 0;
}