高密做网站哪家强价位,成都网站营销推广公司,小程序免费开发制作,永久云服务器购买题目链接#xff1a; 无 题目大意#xff1a; 求一个点到其他所有点的最短距离和#xff0c;保证图连通。 解题过程#xff1a; 刚开始用 Floyd 水过的#xff0c;后来用换了几种方法#xff0c;不错的模板题#xff0c;Floyd 的时候#xff0c;要用 vector 存边#… 题目链接 无 题目大意 求一个点到其他所有点的最短距离和保证图连通。 解题过程 刚开始用 Floyd 水过的后来用换了几种方法不错的模板题Floyd 的时候要用 vector 存边否则超内存。 题目分析 略 AC代码Dijkstra SPFA #includebits/stdc.h
using namespace std;const int MAX 11234, INF 0x3f3f3f3f;vectorint edges[MAX];
int dist[MAX], book[MAX];void spfa(int s) {memset(dist, INF, sizeof(dist));memset(book, 0, sizeof(book));queueint q;q.push(s);book[s] 1;dist[s] 0;while (!q.empty()) {int u q.front();for (int i 0; i edges[u].size(); i) {int v edges[u][i];if (dist[v] dist[u] 1) {dist[v] dist[u] 1;if (!book[v]) {q.push(v);book[v] 1;}}}q.pop();book[u] 0;}
}void dijkstra(int s) {memset(dist, INF, sizeof(dist));priority_queuepairint, int q;dist[s] 0;q.push(make_pair(-dist[s], s));while (!q.empty()) {int u q.top().second;q.pop();for (int i 0; i edges[u].size(); i) {int v edges[u][i];if (dist[v] dist[u] 1) {dist[v] dist[u] 1;q.push(make_pair(-dist[v], v));}}}
}int main() {int n, m;scanf(%d %d, n, m);while (m--) {int u, v;scanf(%d %d, u, v);edges[u].push_back(v);edges[v].push_back(u);}int k;scanf(%d, k);while (k--) {int s;scanf(%d, s);dijkstra(s);int sum 0;for (int i 1; i n; i) {if (i s)continue;sum dist[i];}printf(Cc(%d)%.2f\n, s, (n-1.0)/sum);}
}AC代码Floyd #includebits/stdc.h
using namespace std;
const int INF 0x3f3f3f3f, MAX 10001;int main()
{vectorintedge[MAX];int n, m;scanf(%d %d, n, m);for (int i 0; i n; i) {for (int j 0; j n; j) {edge[i].push_back(INF);}}for (int i 1; i n; i) {edge[i][i] 0;}for (int i 0; i m; i) {int u, v;scanf(%d %d, u, v);edge[u][v] edge[v][u] 1;}for (int k 1; k n; k) {for (int i 1; i n; i) {for (int j 1; j n; j) {if (edge[i][j] edge[i][k] edge[k][j])edge[i][j] edge[i][k] edge[k][j];}}}int k;scanf(%d, k);while (k--) {int c;scanf(%d, c);double sum 0;for (int i 1; i n; i) {if (i c)continue;sum edge[c][i];}printf(Cc(%d)%.2f\n, c, (n-1)/sum);}
}转载于:https://www.cnblogs.com/ACMFish/p/7222852.html
