@[KevinYu](/space/show?uid=105496) 同
by 蒟蒻wyx @ 2018-11-09 20:27:48
@[蒟蒻wyx](/space/show?uid=34511) 已解决;
1.开long long
2.dij跑错了
by KevinYu @ 2018-11-09 21:03:36
@[KevinYu](/space/show?uid=105496) 怎么跑错了？
by 蒟蒻wyx @ 2018-11-09 21:13:17
@[蒟蒻wyx](/space/show?uid=34511) 我把我第二次代码发给你吧。
我不好解释
```cpp
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<climits>
#include<algorithm>
#include<complex>
#include<map>
#include<queue>
#include<vector>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
struct edge
{
ll to,next,weight;
}a[2000020],p[2000020];
struct node
{
ll dist,id;
node(){}
node(ll dist,ll id):dist(dist),id(id){}
};
bool operator <(node xi,node yi)
{
return xi.dist>yi.dist;
}
ll n,m,k,s;
ll cnp(0),cnt(0);
ll head[1000010];
ll dist[1000010];
ll vis[1000010];
ll headp[1000010];
ll dng[1000010];
ll pre[1000010];
pair<ll,ll>ed[1000010];
ll x,y,w;
ll csp,csq;
void addedge(ll xi,ll yi,ll wi)
{
a[cnt].to=yi;
a[cnt].next=head[xi];
a[cnt].weight=wi;
head[xi]=cnt++;
}
void preadd(ll xi,ll yi,ll wi)
{
p[cnp].to=yi;
p[cnp].next=headp[xi];
p[cnp].weight=wi;
headp[xi]=cnp++;
}
void dijkstra(ll s0)
{
memset(pre,-1,sizeof(pre));
memset(vis,0,sizeof(vis));
memset(dist,INF,sizeof(dist));
priority_queue<node> q;
q.push(node(0,s0));
dist[s0]=0;
while(!q.empty())
{
node t(q.top());
q.pop();
if(vis[t.id])continue;
vis[t.id]=1;
for(ll i=head[t.id];i!=-1;i=a[i].next)
{
ll v=a[i].to;
if(dist[v]>a[i].weight+t.dist)
{
pre[v]=t.id;
dist[v]=a[i].weight+t.dist;
q.push(node(dist[v],v));
}
}
}
}
void predij(ll s0)
{
memset(vis,0,sizeof(vis));
memset(dist,INF,sizeof(dist));
priority_queue<node> q;
q.push(node(0,s0));
dist[s0]=0;
while(!q.empty())
{
node t(q.top());
q.pop();
if(vis[t.id])continue;
vis[t.id]=1;
for(ll i=headp[t.id];i!=-1;i=p[i].next)
{
ll v=p[i].to;
if(dist[v]>p[i].weight+t.dist)
{
dist[v]=p[i].weight+t.dist;
q.push(node(dist[v],v));
}
}
}
}
int main()
{
memset(head,-1,sizeof(head));
memset(headp,-1,sizeof(headp));
scanf("%lld%lld%lld%lld",&n,&m,&k,&s);
scanf("%lld%lld",&csp,&csq);
for(ll i=1;i<=k;i++)
{
scanf("%lld",&x);
preadd(n+1,x,0);
}
for(ll i=1;i<=m;i++)
{
scanf("%lld%lld",&x,&y);
ed[i].first=x;
ed[i].second=y;
preadd(x,y,1);
preadd(y,x,1);
}
predij(n+1);
for(ll i=1;i<=n;i++)
{
if(i==1||i==n)dng[i]=0;
else if(dist[i]==0)dng[i]=INF;
else if(dist[i]<=s)dng[i]=csq;
else dng[i]=csp;
}
for(ll i=1;i<=m;i++)
{
addedge(ed[i].first,ed[i].second,dng[ed[i].first]+dng[ed[i].second]);
addedge(ed[i].second,ed[i].first,dng[ed[i].first]+dng[ed[i].second]);
}
dijkstra(1);
printf("%lld\n",dist[n]/2);
return 0;
}
```
by KevinYu @ 2018-11-10 05:33:54