注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Memento

这是一间记忆仓库~~

 
 
 

日志

 
 

POJ 4046 Sightseeing  

2012-05-14 19:41:33|  分类: 图论 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
       金华邀请赛的C题,卡常数卡的厉害,幸好比赛的时候没开此题,不然就悲剧了。算法很简单,做n次单源最短路,每次只在不比起始点的费用大的点上走。然后对于每个询问,枚举从s到t路径上经过的费用最大的点,最后得出答案。复杂度为O(n*n*log(n)+q*n)。不过直接这么些是很可能超时的,必须先把询问读进来,然后每做一次最短路就更新一下q个询问的答案,这样相当于换了一下循环的顺序,但结果就从TLE变成了AC,真是坑爹.........

#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
#define N 1009
#define ll long long
using namespace std;

struct edge{
int v,w;
edge *nxt;
}E[100000],*ep,*Adj[N];

struct state{
int v;
ll c;
};

struct cmp{
bool operator ()(const state &i,const state &j)
{
return i.c>j.c;
}
};

int n,m,q;
int price[N],s[20009],e[20009];
//bool vis[N];
ll ans[20009],d[N];

void addedge(int u,int v,int w)
{
ep->v=v,ep->w=w,ep->nxt=Adj[u];
Adj[u]=ep++;
}

void dij(int start)
{
state p,t;
priority_queue<state,vector<state>,cmp> Q;
memset(d,-1,sizeof(d));
//memset(vis,0,sizeof(vis));
t.v=start;
t.c=d[start]=0;
Q.push(t);
while(!Q.empty()){
p=Q.top();
Q.pop();
if(p.c!=d[p.v]) continue;
for(edge *i=Adj[p.v];i;i=i->nxt)
if(price[i->v]<=price[start]&&(d[i->v]==-1||p.c+i->w<d[i->v]))
{
t.v=i->v;
t.c=d[i->v]=p.c+i->w;
Q.push(t);
}
}
}

void update(ll &a,ll b){a=(a==-1||b<a)?b:a;}

int main()
{
while(scanf("%d%d",&n,&m),n)
{
ep=E;
memset(Adj,0,sizeof(Adj));
memset(ans,-1,sizeof(ans));
for(int i=1;i<=n;i++) scanf("%d",price+i);
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
addedge(x,y,z);
addedge(y,x,z);
}
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
scanf("%d%d",s+i,e+i);
if(price[s[i]]<price[e[i]]) swap(s[i],e[i]);
}
for(int i=1;i<=n;i++)
{
dij(i);
for(int j=1;j<=q;j++)
if(d[s[j]]!=-1&&d[e[j]]!=-1)
update(ans[j],d[s[j]]+d[e[j]]+max(price[i],price[s[j]]));
}
for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);
puts("");
}
}


  评论这张
 
阅读(290)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017