理解算法以后刷刷模板题，颓废的一天就过去了。。。（真的理解了吗）
poj 2449
k短路模板题
#include<cstdio>
#include<vector>
#include<queue>
#define inf 2e8
#define C (c=getchar())
using namespace std;
inline void read(int &a)
{
static char c;C;a=0;
while(c<'0'||c>'9')C;
while(c>='0'&&c<='9')a=a*10+c-'0',C;
}
struct edge{
int to,x;
};
struct heap{
int g,f,to;
bool operator < (const heap &a) const {
if(a.f==f) return a.g<g;
else return a.f<f;
}
};
vector<edge>e[1010];
vector<edge>e1[1010];
int n,m,s,t,k;
int vis[1010],dis[1010],ans;
inline void add(int x,int y,int z){e1[x].push_back((edge){y,z});};
inline void add1(int x,int y,int z){e[x].push_back((edge){y,z});};
queue<int>Q;
int spfa(int s,int t)
{
for(int i=1;i<=n;++i) dis[i]=inf;
dis[s]=0;
Q.push(s);
vis[s]=1;
while(!Q.empty())
{
int x=Q.front();Q.pop();
for(int i=0;i<e[x].size();++i)
if(dis[x]+e[x][i].x<dis[e[x][i].to])
{
dis[e[x][i].to]=e[x][i].x+dis[x];
if(!vis[e[x][i].to])
{
Q.push(e[x][i].to);
vis[e[x][i].to]=1;
}
}
vis[x]=0;
}
if(dis[t]==inf) return -1;
return 0;
}
priority_queue<heap> h;
int a_star()
{
if(s==t) ++k;
int cnt=0;
heap tmp,tmp1;
tmp.to=s;
tmp.g=0;
tmp.f=tmp.g+dis[tmp.to];
h.push(tmp);
while(!h.empty())
{
tmp=h.top();h.pop();
if(tmp.to==t) ++cnt;
if(cnt==k) return tmp.g;
for(int i=0;i<e1[tmp.to].size();++i)
{
tmp1.to=e1[tmp.to][i].to;
tmp1.g=tmp.g+e1[tmp.to][i].x;
tmp1.f=tmp1.g+dis[tmp1.to];
h.push(tmp1);
}
}
return -1;
}
int main()
{
read(n),read(m);
int x,y,z;
for(int i=1;i<=m;++i)
{
read(x),read(y),read(z);
add(x,y,z);
add1(y,x,z);
}
read(s),read(t),read(k);
if(spfa(t,s)==-1) ans=inf;
else ans=a_star();
printf("%d",ans==inf?-1:ans);
return 0;
}
------------------------------------------------------------
bzoj 1598
来自usaco的k短路裸题
把模板改几句话就好
#include<cstdio>
#include<vector>
#include<queue>
#define inf 2e8
#define C (c=getchar())
using namespace std;
inline void read(int &a)
{
static char c;C;a=0;
while(c<'0'||c>'9')C;
while(c>='0'&&c<='9')a=a*10+c-'0',C;
}
struct edge{
int to,x;
};
struct heap{
int g,f,to;
bool operator < (const heap &a) const {
if(a.f==f) return a.g<g;
else return a.f<f;
}
};
vector<edge>e[1010];
vector<edge>e1[1010];
int n,m,s,t,k;
int vis[1010],dis[1010],ans[1010];
inline void add(int x,int y,int z){e1[x].push_back((edge){y,z});};
inline void add1(int x,int y,int z){e[x].push_back((edge){y,z});};
queue<int>Q;
int spfa(int s,int t)
{
for(int i=1;i<=n;++i) dis[i]=inf;
dis[s]=0;
Q.push(s);
vis[s]=1;
while(!Q.empty())
{
int x=Q.front();Q.pop();
for(int i=0;i<e[x].size();++i)
if(dis[x]+e[x][i].x<dis[e[x][i].to])
{
dis[e[x][i].to]=e[x][i].x+dis[x];
if(!vis[e[x][i].to])
{
Q.push(e[x][i].to);
vis[e[x][i].to]=1;
}
}
vis[x]=0;
}
if(dis[t]==inf) return -1;
return 0;
}
priority_queue<heap> h;
void a_star()
{
if(s==t) ++k;
int cnt=0;
heap tmp,tmp1;
tmp.to=s;
tmp.g=0;
tmp.f=tmp.g+dis[tmp.to];
h.push(tmp);
while(!h.empty())
{
tmp=h.top();h.pop();
if(tmp.to==t) ans[++cnt]=tmp.g;
if(cnt==k) return;
for(int i=0;i<e1[tmp.to].size();++i)
{
tmp1.to=e1[tmp.to][i].to;
tmp1.g=tmp.g+e1[tmp.to][i].x;
tmp1.f=tmp1.g+dis[tmp1.to];
h.push(tmp1);
}
}
}
int main()
{
read(n),read(m),read(k);
int x,y,z;
for(int i=1;i<=m;++i)
{
read(x),read(y),read(z);
add(x,y,z);
add1(y,x,z);
}
s=n;t=1;
if(spfa(t,s)==-1)
for(int i=1;i<=k;++i) ans[i]=inf;
else a_star();
for(int i=1;i<=k;++i)
if(ans[i]==0||ans[i]==inf) printf("-1\n");
else printf("%d\n",ans[i]);
return 0;
}
------------------------------------------------------------
bzoj 1975
k短路裸题
把模板改几句话就好了
#include<cstdio>
#include<vector>
#include<queue>
#define inf 2e8
#define C (c=getchar())
using namespace std;
inline void read(int &a)
{
static char c;C;a=0;
while(c<'0'||c>'9')C;
while(c>='0'&&c<='9')a=a*10+c-'0',C;
}
struct edge{
int to;
double x;
};
struct heap{
int to;
double g,f;
bool operator < (const heap &a) const {
if(a.f==f) return a.g<g;
else return a.f<f;
}
};
vector<edge>e[5010];
vector<edge>e1[5010];
int n,m,s,t,ans;
double hav,tot;
int vis[5010];
double dis[5010];
inline void add(int x,int y,double z){e1[x].push_back((edge){y,z});};
inline void add1(int x,int y,double z)
{
e[x].push_back((edge){y,z});
}
queue<int>Q;
void spfa(int s,int t)
{
for(int i=1;i<=n;++i) dis[i]=inf;
dis[s]=0;
Q.push(s);
vis[s]=1;
while(!Q.empty())
{
int x=Q.front();Q.pop();
for(int i=0;i<e[x].size();++i)
if(dis[x]+e[x][i].x<dis[e[x][i].to])
{
dis[e[x][i].to]=e[x][i].x+dis[x];
if(!vis[e[x][i].to])
{
Q.push(e[x][i].to);
vis[e[x][i].to]=1;
}
}
vis[x]=0;
}
}
priority_queue<heap> h;
void a_star()
{
if(s==t) ++ans;
int cnt=0;
heap tmp,tmp1;
tmp.to=s;
tmp.g=0;
tmp.f=tmp.g+dis[tmp.to];
h.push(tmp);
while(!h.empty())
{
tmp=h.top();h.pop();
if(tmp.to==t&&hav+tmp.g<=tot)hav=hav+tmp.g,++ans;
if(hav+tmp.g>tot) return;
for(int i=0;i<e1[tmp.to].size();++i)
{
tmp1.to=e1[tmp.to][i].to;
tmp1.g=tmp.g+e1[tmp.to][i].x;
tmp1.f=tmp1.g+dis[tmp1.to];
h.push(tmp1);
}
}
}
int main()
{
read(n),read(m),scanf("%lf",&tot);
int x,y;double z;
for(int i=1;i<=m;++i)
{
read(x),read(y),scanf("%lf",&z);
add(x,y,z);
add1(y,x,z);
}
s=1;t=n;
spfa(t,s);
a_star();
printf("%d\n",ans);
return 0;
}