L3-007 天梯地图

解题思路：其实就是用两次dijkstra算法分别用于求时间，和求最短路。虽然代码长，但其实写的时间不长。后一个dijkstra复制一下前面，再稍微修改一下即可。

#include<cstdio>
#include<cstring>
#include<set>
#include<iterator>
#include<algorithm>
#include<vector>
#include<queue>
#define inf 100000000
using
namespace std;
struct node
{
int v,t,d;
node(){
}
node(int v,int t,int d):v(v),t(t),d(d){
}
};
int dis[501],vis[501],tim[501],nod[501];
int pret[501],pred[501],mt,md;
int st,ed,n;
vector<node> s[500];
void dis_dijkstra()
{
int u=st;
pred[st]=-1;
for(int i=0;i<n;i++)
{
dis[i]=inf;
vis[i]=0;
nod[i]=inf;
}
dis[st]=0;
nod[st]=0;
for(int i=0;i<n;i++)
{
int tp=inf,k=-1;
for(int j=0;j<n;j++)
{
if(!vis[j]&&dis[j]<tp)
{
tp=dis[j];
k=j;
}
}
u=k;
if(k==-1)break;
vis[k]=1;
for(int j=0;j<s[k].size();j++)
{
int v=s[k][j].v,d=s[k][j].d;
if(!vis[v]&&dis[v]>dis[k]+d)
{
dis[v]=dis[k]+d;
nod[v]=nod[k]+1;
pred[v]=k;
}else
if(dis[v]==dis[k]+d&&nod[v]>nod[k]+1)
{
nod[v]=nod[k]+1;
pred[v]=k;
}
}
}
md=dis[ed];
}
void tim_dijkstra()
{
int u=st;
pret[st]=-1;
for(int i=0;i<n;i++)
{
dis[i]=inf;
vis[i]=0;
tim[i]=inf;
}
dis[st]=0;
tim[st]=0;
for(int i=0;i<n;i++)
{
int tp=inf,k=-1;
for(int j=0;j<n;j++)
{
if(!vis[j]&&tim[j]<tp)
{
tp=tim[j];
k=j;
}
}
u=k;
if(k==-1)break;
vis[k]=1;
for(int j=0;j<s[k].size();j++)
{
int v=s[k][j].v,d=s[k][j].d,t=s[k][j].t;
if(!vis[v]&&tim[v]>tim[k]+t)
{
tim[v]=tim[k]+t;
dis[v]=dis[k]+d;
pret[v]=k;
}else
if(tim[v]==tim[k]+t&&dis[v]>dis[k]+d)
{
dis[v]=dis[k]+d;
pret[v]=k;
}
}
}
mt=tim[ed];
}
int main()
{
//freopen("t.txt","r",stdin);
int a,b,c,d,e,m;
int stckt[506],topt,stckd[506],topd;
scanf("%d%d",&n,&m);
while(m--)
{
scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);
s[a].push_back(node(b,e,d));
if(c==0)
{
s[b].push_back(node(a,e,d));
}
}
scanf("%d%d",&st,&ed);
tim_dijkstra();
topt=0,topd=0;
//printf("%d",mt);
for(int i=ed;i!=-1;i=pret[i])
stckt[topt++]=i;
dis_dijkstra();
for(int i=ed;i!=-1;i=pred[i])
stckd[topd++]=i;
bool fg=true;
if(topt!=topd)
fg=false;
else
{
for(int i=0;i<topt;i++)
{
if(stckt[i]!=stckd[i])
{
fg=false;
break;
}
}
}
if(fg)
{
printf("Time = %d; Distance = %d: %d",mt,md,stckt[--topt]);
for(int i=topt-1;i>=0;i--)
printf(" => %d",stckt[i]);
}else
{
printf("Time = %d: %d",mt,stckt[--topt]);
for(int i=topt-1;i>=0;i--)
printf(" => %d",stckt[i]);
printf("n");
printf("Distance = %d: %d",md,stckd[--topd]);
for(int i=topd-1;i>=0;i--)
printf(" => %d",stckd[i]);
}
return
0;
}

最后

以上就是稳重鸭子为你收集整理的L3-007 天梯地图的全部内容，希望文章能够帮你解决L3-007 天梯地图所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。