生活随笔
收集整理的这篇文章主要介绍了
hdu 2680 Choose the best route
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=2680
简单最短路问题。。。。。
运行结果：
| Accepted | 2680 | 265MS | 4164K | 1382 B | C++ |
//dijkstra
#include<stdio.h>
#define INF (1<<30)
#define MAXN 1005
int map[MAXN][MAXN],n,m,s,d[MAXN],dis[MAXN];
bool vis[MAXN];
void dijkstra(int start)
{int i,j,k;for(i = 1; i <= n; i++)//初始化所有点为未访问过，起点到所有其他点的距离为无穷远vis[i] = false,dis[i] = INF;//将起点到个顶点的距离保存在dis数组中for(i = 1; i <= n; i++)dis[i] = map[start][i];//起点到其本身的距离为0，并将其标记为已经访问过dis[start] = 0;vis[start] = true;//在将n-1个顶点加入到最短路中for(i = 1; i < n; i++){int min = INF;for(j = 1; j <= n; j++){if(!vis[j] && dis[j] < min){min = dis[j];k = j;}}if(min == INF)continue;vis[k] = true;for(j = 1; j <= n; j++){if( !vis[j] && dis[j] > min + map[k][j])dis[j] = min + map[k][j];}}
}
int main()
{int i,j,start,end,cost,w;while(scanf("%d%d%d",&n,&m,&s) != EOF){for(i = 0; i <= n; i++)for(j = 0; j <= n; j++){map[i][j] = (i == j ? 0 : INF);}for(i = 0; i < m; i++){scanf("%d%d%d",&end,&start,&cost);if(map[start][end] > cost)map[start][end] = cost;}dijkstra(s);scanf("%d",&w);int min = INF;while( w-- ){scanf("%d",&end);if(dis[end] < min)min = dis[end];}if(min == INF)printf("-1\n");elseprintf("%d\n",min);}return 0;
}
运行结果：
| Accepted | 2680 | 125MS | 496K | 1270 B | C++ |
//spfa
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define INF (1<<30)
struct node
{int v,cost;node *next;
}*head[1005],edge[20005];
int dis[1005];
bool vis[1005];
int n,m,s;
queue<int> que;
void spfa(int start)
{int i = 0;for(i = 1; i <= n; i++)dis[i] = INF;memset(vis,false,sizeof(vis));vis[start] = true;dis[start] = 0;que.push(start);while( !que.empty() ){int now = que.front();que.pop();vis[now] = false;for(node *p = head[now]; p ; p = p->next){if(dis[p->v] > dis[now] + p->cost){dis[p->v] = dis[now] + p->cost;if( !vis[p->v]){vis[p->v] = true;que.push(p->v);}}}}
}
int main()
{int i,start,end,cost,w,min;node *p;while(scanf("%d%d%d",&n,&m,&s) != EOF){for(i = 1; i <= n; i++)head[i] = NULL;p = edge;for(i = 0; i < m; i++){scanf("%d%d%d",&start,&end,&cost);p->v = start;p->cost = cost;p->next = head[end];head[end] = p++;}spfa(s);scanf("%d",&w);min = INF;while( w-- ){scanf("%d",&start);if(dis[start] < min)min = dis[start];}if(min == INF)printf("-1\n");elseprintf("%d\n",min);}return 0;
}
转载于:https://www.cnblogs.com/LUO257316/archive/2012/09/03/3220864.html
总结
以上是生活随笔为你收集整理的hdu 2680 Choose the best route的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
