|
题意：
思路：对每个输入的点跑一遍dijkstra算法，然后对这个点到所有点的距离求和按公式输出就可以了。
（这次尝试了用数组模拟链表来做最短路问题，刷新了自己对最短路的理解）
这里构造链表的过程我的理解一直有误差，第一行的式子中参与代码构建的是Next[cnt] = head[y];head[y] = cnt++;这两个语句。而前边的只是存了编号为cnt的边的另一个端点和这条边的花费。
讲解见大佬博客：https://blog.csdn.net/major_zhang/article/details/52155279
代码：
#include <iostream>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <vector>
#define INF 0x3f3f3f3f
#define FRE() freopen("in.txt","r",stdin)
using namespace std;
typedef long long ll;
typedef pair<int,string> P;
const int maxn = 20000;
int Next[maxn],head[maxn],u[maxn],cost[maxn];
int dist[maxn],vis[maxn];
int n,m;
int cnt = 0;
void InsertEdge(int x,int y) {
u[cnt] = x;cost[cnt] = 1;Next[cnt] = head[y];head[y] = cnt++;
u[cnt] = y;cost[cnt] = 1;Next[cnt] = head[x];head[x] = cnt++;
}
void init() {
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
for(int i = 0; i<m; i++) {
int st,en;
scanf("%d%d",&st,&en);
InsertEdge(st,en);
}
}
void Dijkstra(int v) {
memset(dist,INF,sizeof(dist));
for(int i = head[v]; ~i ; i = Next[i]) {
dist[u[i]] = cost[i];
}
memset(vis,0,sizeof(vis));
vis[v] = 1;
dist[v] = 0;
while(1) {
int t = -1;
for(int i = 1; i<=n; i++) {//寻找当前点的序列中还没有访问的最小的距离的点，这里的i指的是点
if(!vis[i] && (t==-1 || dist[t]>dist[i]))
t = i;
}
if(t == -1)
break;
vis[t] = 1;
for(int i = head[t]; ~i; i = Next[i]) {//从与该点相连的边找最小的花费，这里的i其实是表示的标号cnt
if(dist[u[i]] > dist[t]+cost[i]){
dist[u[i]] = dist[t]+cost[i];
}
//dist[u[i]] = min(dist[u[i]], dist[t]+cost[i]);
}
}
bool ok = false;
int sum = 0;
for(int i = 1; i<=n; i++) {
if(dist[i]==INF) {
ok = true;
//cout<<"GG"<<endl;
break;
}
sum += dist[i];
}
// printf("sum: %d n: %d\n",sum,n);
if(ok)
printf("Cc(%d)=0.00\n",v);
else
printf("Cc(%d)=%.2f\n",v,(1.0*(n-1))/(1.0*sum));
}
int main() {
//FRE();
int n,m;
init();
int num,t;
scanf("%d",&num);
for(int i = 0; i<num; i++) {
scanf("%d",&t);
Dijkstra(t);
}
return 0;
}
| 
转播
