题目分析 :
for(int i=0;i<=k;++i) f[s][i]=0
Code:
#include <bits/stdc++.h>
using namespace std;
#define maxn 60
#define maxm 1010
#define maxk 55
#define INF 9187201950435737471
int n,m,k,s,t,head[maxn],size=0;
long long f[maxn][maxk];
bool vis[maxn][maxk];
struct edge {
int v,nxt,w;
}e[maxm<<1];
struct hepnode {
int pos,AKIOI;
long long dis;
bool operator < (const hepnode& rhs) const {
return dis > rhs.dis;
}
};
inline int read_() {
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=(x<<1)+(x<<3)+c-'0';
c=getchar();
}
return x*f;
}
inline void clean_() {
memset(head,-1,sizeof(head));
memset(f,0x7f,sizeof(f));
memset(vis,false,sizeof(vis));
}
inline void add_(int u,int v,int w) {
e[++size].v=v;
e[size].w=w;
e[size].nxt=head[u];
head[u]=size;
}
inline void Dijkstra_() {
for(int i=0;i<=k;++i) {
f[s][i]=0;
}
priority_queue<hepnode>q;
q.push( (hepnode) {s,0,f[s][0]} );
vis[s][0]=true;
while(!q.empty()) {
hepnode pdc=q.top();
q.pop();
int u=pdc.pos,AKNOI=pdc.AKIOI;
vis[u][AKNOI]=false;
for(int i=head[u];~i;i=e[i].nxt) {
int v=e[i].v,w=e[i].w;
if(f[v][0]==INF||f[v][0]>f[u][0]+w) {
f[v][0]=f[u][0]+w;
if(!vis[v][0]) {
vis[v][0]=true;
q.push( (hepnode) {v,0,f[v][0]} );
}
}
for(int j=1;j<=k;++j) {
if(f[v][j]>min(f[u][j-1]+(w/2),f[u][j]+w)) {
f[v][j]=min(f[u][j-1]+(w/2),f[u][j]+w);
if(!vis[v][j]) {
vis[v][j]=true;
q.push( (hepnode) {v,j,f[v][j]} );
}
}
}
}
}
printf("%lld",f[t][k]);
}
void readda_() {
n=read_();m=read_();k=read_();
s=1;t=n;
clean_();
int x,y,z;
for(int i=1;i<=m;++i) {
x=read_();y=read_();z=read_();
add_(x,y,z);add_(y,x,z);
}
Dijkstra_();
}
int main() {
freopen("a.txt","r",stdin);
readda_();
return 0;
}