逃跑(escape)
时间限制: 3 Sec 内存限制: 128 MB
题目描述
输入
第一行是5个正整数,n,m,k,S,T,分别代表无向图点数,边数,蝙蝠的数量,二小姐所在起点的编号,目标点的编号。
第二行是k个正整数,分别代表大小姐每个蝙蝠所在的起点的编号。接下来有m行,每行有4个正整数,u,v,q,p,分别是该边的起点、终点,蝙蝠通过该
路花费的代价,二小姐通过该路花费的代价。
输出
一行,一个整数,所有人物达到终点所需要的代价的和的最小值。
样例输入
5 5 2 3 4
1 5
1 2 3 5
3 2 3 5
2 4 4 9
3 4 9 6
5 4 1 1
样例输出
13
题解:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<stack>
#include<algorithm>
#include<ctime>
#include<vector>
using namespace std;
int n,m,a,src,des;
struct node
{
int next,to;
long long dis,dis2;
}edge[];
int head[],size=;
int b[];//蝙蝠所在点
long long v1[];//各点到终点
long long v2[];//二小姐到各点
long long v3[];
void putin(int from,int to,long long dis,long long dis2)
{
size++;
edge[size].next=head[from];
edge[size].to=to;
edge[size].dis=dis;
edge[size].dis2=dis2;
head[from]=size;
}
void in(int from,int to,long long dis,long long dis2)
{
putin(from,to,dis,dis2);
putin(to,from,dis,dis2);
}
void bfs1()
{
memset(v1,/,sizeof(v1));
int front=,tail=,i,j;
int p[],vis[]={};
p[tail++]=des;
v1[des]=;
vis[des]=;
while(front!=tail)
{
int x=p[front++];
front%=;
vis[x]=;
for(i=head[x];i!=-;i=edge[i].next)
{
int y=edge[i].to;
if(v1[y]>v1[x]+edge[i].dis)
{
v1[y]=v1[x]+edge[i].dis;
if(!vis[y])
{
vis[y]=;
p[tail++]=y;
tail%=;
}
}
}
}
}
void bfs2()
{
memset(v2,/,sizeof(v2));
int front=,tail=,i,j;
int p[],vis[]={};
p[tail++]=src;
v2[src]=;
vis[src]=;
while(front!=tail)
{
int x=p[front++];
front%=;
vis[x]=;
for(i=head[x];i!=-;i=edge[i].next)
{
int y=edge[i].to;
if(v2[y]>v2[x]+edge[i].dis2)
{
v2[y]=v2[x]+edge[i].dis2;
if(!vis[y])
{
vis[y]=;
p[tail++]=y;
tail%=;
}
}
}
}
}
void bfs3()
{
memset(v3,,sizeof(v3));
int front=,tail=,i,j;
int p[],vis[]={};
for(i=;i<=a;i++)
{
p[tail++]=b[i];
v3[b[i]]=v1[b[i]];
vis[b[i]]=;
}
while(front!=tail)
{
int x=p[front++];
front%=;
vis[x]=;
for(i=head[x];i!=-;i=edge[i].next)
{
int y=edge[i].to;
if(v3[y]<v3[x]-edge[i].dis)
{
v3[y]=v3[x]-edge[i].dis;
if(!vis[y])
{
vis[y]=;
p[tail++]=y;
tail%=;
}
}
}
}
}
long long ans,ans1;
int main()
{
memset(head,-,sizeof(head));
int i,j;
scanf("%d%d%d%d%d",&n,&m,&a,&src,&des);
for(i=;i<=a;i++)
scanf("%d",&b[i]);
for(i=;i<=m;i++)
{
int from,to;long long dis,dis2;
scanf("%d%d%lld%lld",&from,&to,&dis,&dis2);
in(from,to,dis,dis2);
}
bfs1();bfs2();bfs3();
ans+=v2[des];
for(i=;i<=a;i++)
ans+=v1[b[i]];
ans1=ans;
for(i=;i<=n;i++)
{
ans1=min(ans1,ans-v2[des]+v2[i]+v1[i]-v3[i]);
}
cout<<ans1;
return ;
}