九度:题目1008:最短路径问题

发布时间:2017-2-20 0:30:55 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"九度:题目1008:最短路径问题",主要涉及到九度:题目1008:最短路径问题方面的内容,对于九度:题目1008:最短路径问题感兴趣的同学可以参考一下。

题目描述: 给你n个点,m条无向边,每条边都有长度d和花费p,给你起点s终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。 输入: 输入n,m,点的编号是1~n,然后是m行,每行4个数 a,b,d,p,表示a和b之间有一条边,且其长度为d,花费为p。最后一行是两个数 s,t;起点s,终点t。n和m为0时输入结束。 (1<n<=1000, 0<m<100000, s != t) 输出: 输出 一行有两个数, 最短距离及其花费。 样例输入: 3 2 1 2 5 6 2 3 4 5 1 3 0 0 样例输出: 9 11 分析: 乍一看像是dijkstra算法,但是还多了一个求最少花费的条件,所以不能找到目标点就返回,必须将所有能到目标点的情况都要遍历到,所以用SPFA算法 #include <stdio.h> #include <stdlib.h> #include <iostream> #include <string> #include <queue> using namespace std; #define MAX 1002 #define INT 0x7fffffff int w[MAX]; int cost[MAX]; bool vis[MAX]; struct node{ int w,cost; }map[MAX][MAX]; int n,m,a,b,d,p,s,t; void SPFA(){ for(int i=1;i<=n;i++){w[i]=INT;cost[i]=INT;vis[i]=false;} queue<int> q; q.push(s); w[s]=0; cost[s]=0; vis[s]=true; while(!q.empty()){ int cur=q.front();q.pop(); vis[cur]=false; for(int i=1;i<=n;i++){ if(map[cur][i].w!=INT&&w[i]>=w[cur]+map[cur][i].w){ w[i]=w[cur]+map[cur][i].w; cost[i]=min(cost[i],cost[cur]+map[cur][i].cost); if(!vis[i]){ vis[i]=true; q.push(i); } } } } } int main(){ //freopen("C:\\in.txt","r",stdin); while(~scanf("%d%d",&n,&m)){ if(!n&&!m)break; for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){map[i][j].w=INT;map[i][j].cost=INT;} for(int i=1;i<=m;i++){ scanf("%d%d%d%d",&a,&b,&d,&p); map[a][b].w=map[b][a].w=d; map[a][b].cost=map[b][a].cost=p; } scanf("%d%d",&s,&t); SPFA(); printf("%d %d\n",w[t],cost[t]); } return 0; } /************************************************************** Problem: 1008 User: starcuan Language: C++ Result: Accepted Time:10 ms Memory:9376 kb ****************************************************************/

上一篇:Eclipse快捷键大全
下一篇:

相关文章

相关评论