1988 Problem E 最短路径问题

问题 E: 最短路径问题
时间限制: 1 Sec 内存限制: 32 MB
献花: 22 解决: 14
[献花][花圈][TK题库]
题目描述

给你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

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <cfloat>
#include <map>
#define INF INT32_MAX
using namespace std;
const int MaxN = 1010;
int
des[MaxN];
bool visited[MaxN] = { false };
int
G[MaxN][MaxN],cost[MaxN][MaxN],C[MaxN];
int N;
void Dijkstra(int s)
{
fill(des, des + N + 1, INF);
fill(C, C + N + 1, INF);
memset(visited, 0, N + 1);
des[s] = 0; C[s] = 0;
for (int i = 1, Min, u ; i <= N; ++i)
{
Min = INF; u = -1;
for (int k = 1; k <= N; ++k)
{
if (!visited[k] && Min > des[k])
{
Min = des[k];
u = k;
}
}
if (u == -1)return;
visited[u] = true;
for (int v = 1; v <= N; ++v)
{
if (!visited[v] && G[u][v] != INF)
{
if (des[v] > des[u] + G[u][v])
{
des[v] = des[u] + G[u][v];
C[v] = C[u] + cost[u][v];
}
else if (des[v] == des[u] + G[u][v] && C[v] > C[u] + G[u][v])
{
C[v] = C[u] + G[u][v];
}
}
}
}
}
int main()
{
#ifdef _DEBUG
freopen("data.txt", "r+", stdin);
#endif // _DEBUG
std::ios::sync_with_stdio(false);
int s,t,m;
while (cin >> N >> m, N)
{
fill(G[0], G[0] + (N + 2) * MaxN,INF);
fill(cost[0], cost[0] + (N + 2) * MaxN, INF);
for (int i = 0; i < m; ++i)
{
int u, v, d, p;
cin >> u >> v >> d >> p;
G[u][v] = G[v][u] = d;
cost[u][v] = cost[v][u] = p;
}
cin >> s >> t;
Dijkstra(s);
cout << des[t] << " " << C[t] << endl;
}
return 0;
}
/**************************************************************
Problem: 1988
User: Sharwen
Language: C++
Result: 升仙
Time:0 ms
Memory:9680 kb
****************************************************************/

最后

以上就是娇气保温杯为你收集整理的1988 Problem E 最短路径问题的全部内容，希望文章能够帮你解决1988 Problem E 最短路径问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。