其它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;
}

最新文章

  1. MySQL基础
  2. nginx优化
  3. docker 组件(c/s)
  4. Android快捷键
  5. Unity3D ShaderLab 静态贴图光照模型
  6. VS2008安装SP1补丁后智能提示从中文变为英文的解决办法
  7. OpenFileDialog使用方法
  8. centos6.5安装vmware-tools
  9. HDU 1561-The more, The Better(树状背包)
  10. sgu 108 Self-numbers II
  11. Lesson: Introduction to JAXP
  12. (转)关闭iptables和SELinux
  13. 对比字节流和字符流,回答为什么FileReader不能用来拷贝图片
  14. babel如此简单
  15. VxWorks6.6 pcPentium BSP 使用说明(三):设备驱动
  16. kuangbin带你飞dp专题-基础dp
  17. python selenium 百度登录
  18. jmeter接口测试实例1-添加学生信息
  19. ORM 的基本操作
  20. js-jquery-插件开发(一)

热门文章

  1. 蚂蚁金服HR电话面
  2. 使用MailMessage发送邮件
  3. Hibernate单表映射学习笔记之一——hibernalnate开发环境配置
  4. nginx 安装遇到的问题
  5. SQL——模糊查询
  6. 51nod1010(枚举+二分)
  7. [JLOI2012]树 倍增优化
  8. php路径问题
  9. JMeter - 实时结果 - InfluxDB和Grafana - 第1部分 - 基本设置
  10. WebSocket Client连接AspNetCore SignalR Json Hub