这段代码的含义 #include <iostream> #include <fstream> #include <vector> #include <queue> #include <climits> using namespace std; const int MAXN = 205; const int INF = INT_MAX; int n; int r[MAXN][MAXN]; // 存储租金 bool vis[MAXN]; // 标记是否被访问过 int dist[MAXN]; // 存储从起点到个点的最短距离 void init() { for (int i = 0; i < MAXN; i++) { for (int j = 0; j < MAXN; j++) { r[i][j] = INF; } vis[i] = false; dist[i] = INF; } } void readData() { ifstream fin("C:\\Users\\8aDA\\Desktop\\input.txt"); fin >> n; for (int i = 1; i < n; i++) { for (int j = i + 1; j <= n; j++) { fin >> r[i][j]; r[j][i] = r[i][j]; // 无向图 } } fin.close(); } void dijkstra() { dist[1] = 0; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push(make_pair(0, 1)); while (!pq.empty()) { int u = pq.top().second; pq.pop(); if (vis[u]) { continue; } vis[u] = true; for (int v = 1; v <= n; v++) { if (!vis[v] && dist[v] > dist[u] + r[u][v]) { dist[v] = dist[u] + r[u][v]; pq.push(make_pair(dist[v], v)); } } } } void writeData() { ofstream fout("C:\\Users\\8aDA\\Desktop\\output.txt"); fout << dist[n] << endl; fout.close(); } int main() { init(); readData(); dijkstra(); writeData(); return 0; }
时间: 2024-04-28 11:22:21 浏览: 89
C++常用的#include头文件总结
这段代码是一个求解最短路径的程序,使用了Dijkstra算法。程序首先初始化了一些变量,包括存储租金、是否被访问过、从起点到个点的最短距离等。然后读取输入数据,构造一个无向图,其中每个节点代表一个城市,边权代表两个城市之间的租金。接着,使用Dijkstra算法求解从起点到终点的最短距离,并将结果输出到文件中。
阅读全文