生活随笔
收集整理的這篇文章主要介紹了
hdu 2680 Choose the best route
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
題目地址：http://acm.hdu.edu.cn/showproblem.php?pid=2680
簡(jiǎn)單最短路問題。。。。。
運(yùn)行結(jié)果：
| 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++)//初始化所有點(diǎn)為未訪問過，起點(diǎn)到所有其他點(diǎn)的距離為無窮遠(yuǎn)vis[i] = false,dis[i] = INF;//將起點(diǎn)到個(gè)頂點(diǎn)的距離保存在dis數(shù)組中for(i = 1; i <= n; i++)dis[i] = map[start][i];//起點(diǎn)到其本身的距離為0，并將其標(biāo)記為已經(jīng)訪問過dis[start] = 0;vis[start] = true;//在將n-1個(gè)頂點(diǎn)加入到最短路中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;
}
運(yùn)行結(jié)果：
| 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;
}
?
轉(zhuǎn)載于:https://www.cnblogs.com/LUO257316/archive/2012/09/03/3220864.html
總結(jié)
以上是生活随笔為你收集整理的hdu 2680 Choose the best route的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
