POJ 3268-Silver Cow Party（dijkstra算法）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了POJ 3268-Silver Cow Party（dijkstra算法），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1759字，纯文字阅读大概需要3分钟。
内容图文
题目大意：给出一个单向带权图和一个点s，求点u，u到s的最短路径和s到u的最短路径之和最大。
对于s到任意点的最短路，直接dijkstra可以求出。
对于任意点到s的最短路，如果将所有边反向然后求一次最短路，容易证明，求出的s到任意点v的最短路s-->v就是原来没有反向的图的v-->s的最短路。
所以先求一次dijkstra，保存此次的结果，然后把所有的边反向，权值不变，再求一次dijkstra，将两次结果加起来，计算它们之中的最大值。
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<queue>
using namespace std;
const int maxn=1010;
const int INF=(1<<29);
struct edge
{
int to;
int dis;
};
struct edge2
{
int from;
int to;
int dis;
};
struct heapnode
{
int di;
int num;
bool operator< (const heapnode j) const
{
return di>j.di;
}
};
edge2 e[100010];
int d[maxn];
int sum[maxn];
int use[maxn];
int n;
vector<edge> G[maxn];
void dijkstra(int s);
int main(void)
{
int i,u,v,p,q,m,ans;
edge ed;
while(scanf("%d%d%d",&n,&m,&q)==3)
{
for(i=1;i<=n;i++)
{
G[i].clear();
}
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&p);
ed.to=v;
ed.dis=p;
G[u].push_back(ed);
e[i].from=u;
e[i].to=v;
e[i].dis=p;
}
dijkstra(q);
for(i=1;i<=n;i++)
{
sum[i]=d[i];
G[i].clear();
}
for(i=1;i<=m;i++)
{
ed.to=e[i].from;
ed.dis=e[i].dis;
G[e[i].to].push_back(ed);
}
dijkstra(q);
ans=0;
for(i=1;i<=n;i++)
{
ans=d[i]+sum[i]>ans?d[i]+sum[i]:ans;
}
printf("%d\n",ans);
}
return 0;
}
void dijkstra(int s)
{
int i,u,p;
heapnode h;
priority_queue<heapnode> heap;
for(i=1;i<=n;i++)
{
d[i]=INF;
use[i]=0;
}
h.di=0;
h.num=s;
d[s]=0;
heap.push(h);
while(heap.empty()==false)
{
h=heap.top();
heap.pop();
u=h.num;
if(use[u]==0)
{
use[u]=1;
p=G[u].size();
for(i=0;i<p;i++)
{
if(d[u]+G[u][i].dis<d[G[u][i].to])
{
d[G[u][i].to]=d[u]+G[u][i].dis;
h.di=d[G[u][i].to];
h.num=G[u][i].to;
heap.push(h);
}
}
}
}
}
原文：http://blog.csdn.net/dilemma729/article/details/44007731
内容总结
以上是互联网集市为您收集整理的POJ 3268-Silver Cow Party（dijkstra算法）全部内容，希望文章能够帮你解决POJ 3268-Silver Cow Party（dijkstra算法）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。