F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
大视野在线测评-欢迎您
[ New Thread ]
Problem 2763 >> 求助怎么T飞了???
yangtuotaiji @ 2019-11-07 20:07:42
[ Quote ] [ Edit ] [ Delete ] 1#
#include<bits/stdc++.h>
const long long N=110010,M=550010;
using namespace std;
int n,m,k,s,t,num,head[N];
long long dis[N];
struct E{
int next,to;
long long w;
}e[M<<1];
struct node{
int u;
long long d;
bool operator < (const node&a) const{return d<a.d;}
};
inline long long Read()
{
long long x=0,f=1;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(isdigit(ch))
{
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return x*f;
}
void Write(long long x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
Write(x/10);
putchar(x%10+'0');
}
inline void adde(int u,int v,long long w)
{
e[++num].next=head[u];
e[num].to=v;
e[num].w=w;
head[u]=num;
}
inline void dijkstra()
{
priority_queue<node>q;
for(register int i=0;i<=k*n+n;++i)
dis[i]=2147483647;
dis[s]=0;
node edg;
edg.u=s,edg.d=0;
q.push(edg);
while(!q.empty())
{
node edg=q.top();
q.pop();
int u=edg.u;
long long d=edg.d;
if(d!=dis[u])
continue;
for(register int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(dis[v]>dis[u]+e[i].w)
{
dis[v]=dis[u]+e[i].w;
node edg;
edg.u=v,edg.d=dis[v];
q.push(edg);
}
}
}
}
int main()
{
n=Read(),m=Read(),k=Read();
s=Read(),t=Read();
int u,v;
long long w;
for(register int i=1;i<=m;++i)
{
u=Read(),v=Read(),w=Read();
adde(u,v,w);
adde(v,u,w);
for(register int j=1;j<=k;++j)
{
adde(u+(j-1)*n,v+j*n,0);
adde(v+(j-1)*n,u+j*n,0);
adde(u+j*n,v+j*n,w);
adde(v+j*n,u+j*n,w);
}
}
for(register int i=1;i<=k;++i)
adde(t+(i-1)*n,t+i*n,0);
dijkstra();
Write(dis[t+k*n]);
}
[Top] [Previous Page] [Next Page]

HOME Back