pta 编程题20 旅游规划
2024-10-17 03:22:52
其它pta数据结构编程题请参见:pta
这个最短路径问题只需要求两点之间的最短路径,因而在Dijikstra算法中当求出目标点的最短路径之后跳出循环即可。
#include <iostream>
using namespace std; struct Node
{
int length;
int price;
}; int V, E;
Node **G; void buildGraph();
void deleteGraph();
void dijkstra(int s, int d);
int findMinDist(Node* dist, bool* collected);
bool cmp(Node a, Node b); int main()
{
int S, D;
cin >> V >> E >> S >> D;
buildGraph();
dijkstra(S, D);
deleteGraph();
return ;
} void buildGraph()
{
int a, b, l, p, i;
G = new Node*[V];
for (a = ; a < V; a++)
{
G[a] = new Node[V];
for (b = ; b < V; b++)
{
G[a][b].length = INT_MAX;
G[a][b].price = INT_MAX;
}
} for (i = ; i < E; i++)
{
cin >> a >> b >> l >> p;
G[a][b].length = l;
G[a][b].price = p;
G[b][a].length = l;
G[b][a].price = p;
}
} void deleteGraph()
{
for (int i = ; i < V; i++)
delete[] G[i];
delete[] G;
} bool cmp(Node a, Node b)
{
if (a.length != b.length)
return a.length < b.length;
else
return a.price < b.price;
} int findMinDist(Node* dist, bool* collected)
{
int minV;
Node minDist;
minDist.length = INT_MAX;
minDist.price = INT_MAX; for (int i = ; i < V; i++)
{
if (!collected[i] && cmp(dist[i], minDist))
{
minDist = dist[i];
minV = i;
}
} if (minDist.length == INT_MAX)
return -;
else
return minV;
} void dijkstra(int s, int d)
{
int v, w;
Node *dist, temp;
bool *collected;
dist = new Node[V];
collected = new bool[V];
for (v = ; v < V; v++)
{
dist[v] = G[s][v];
collected[v] = false;
} dist[s].length = ;
dist[s].price = ;
collected[s] = true; while (true)
{
v = findMinDist(dist, collected);
if (v == d) break;
collected[v] = true; for (w = ; w < V; w++)
{
if (!collected[w] && G[v][w].length < INT_MAX)
{
temp.length = dist[v].length + G[v][w].length;
temp.price = dist[v].price + G[v][w].price;
if (cmp(temp, dist[w]))
dist[w] = temp;
}
}
} cout << dist[d].length << " " << dist[d].price;
delete dist;
delete collected;
}
最新文章
- MySQL基础
- nginx优化
- docker 组件(c/s)
- Android快捷键
- Unity3D ShaderLab 静态贴图光照模型
- VS2008安装SP1补丁后智能提示从中文变为英文的解决办法
- OpenFileDialog使用方法
- centos6.5安装vmware-tools
- HDU 1561-The more, The Better(树状背包)
- sgu 108 Self-numbers II
- Lesson: Introduction to JAXP
- (转)关闭iptables和SELinux
- 对比字节流和字符流,回答为什么FileReader不能用来拷贝图片
- babel如此简单
- VxWorks6.6 pcPentium BSP 使用说明(三):设备驱动
- kuangbin带你飞dp专题-基础dp
- python selenium 百度登录
- jmeter接口测试实例1-添加学生信息
- ORM 的基本操作
- js-jquery-插件开发(一)