解题思路:
把里面的结点信息变为vector来表示
注意事项:
vector是一个容器可以用来存放任何类型(包括自定义数据)的数据
参考代码:
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <vector> #include <queue> using namespace std; const int maxn = 10e8; struct Edge{ int to; int dis; bool friend operator < (Edge x, Edge y){ return x.dis > y.dis; } }temp, now; int tag[55]; //标记数组 int dist[55]; //距离数组 计算距离 vector <Edge> vec[55];//类似于链表保存各个结点的信息 int n; void init(){ for(int i = 1; i <= n; i++){ dist[i] = maxn; } memset(tag, 0, sizeof(tag)); } void dij(int f){ priority_queue <Edge> q; init(); temp.to = f; temp.dis = 0; q.push(temp); dist[f] = 0; while(!q.empty()){ now = q.top(); q.pop(); if(!tag[now.to]){ tag[now.to] = 1; for(int i = 0; i < vec[now.to].size(); i++){ if(!tag[vec[now.to][i].to] && dist[now.to] + vec[now.to][i].dis < dist[vec[now.to][i].to]){ dist[vec[now.to][i].to] = dist[now.to] + vec[now.to][i].dis; temp.to = vec[now.to][i].to; temp.dis = dist[vec[now.to][i].to]; q.push(temp); } } } } } int main(){ int f; int tmp; scanf("%d %d", &n, &f); for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ scanf("%d", &tmp); if(tmp != 0){ temp.to = j; temp.dis = tmp; vec[i].push_back(temp); } } } dij(f+1); for(int i = 1; i <= n; i++){ if(i != f+1){ if(dist[i] == maxn){ printf("-1 "); }else{ printf("%d ", dist[i]); } } } return 0; }
0.0分
4 人评分
【蟠桃记】 (C语言代码)浏览:703 |
ASCII帮了大忙浏览:790 |
输出正反三角形 (C语言代码)浏览:857 |
三角形 (C++代码)递推浏览:822 |
【绝对值排序】 (C语言代码)浏览:892 |
C语言程序设计教程(第三版)课后习题8.6 (C语言代码)浏览:590 |
C语言程序设计教程(第三版)课后习题9.2 (C语言代码)浏览:572 |
文科生的悲哀 (C语言代码)浏览:1534 |
有关字符,字符串的输入输出函数说明浏览:497 |
星期判断机 (C语言代码)浏览:888 |