题意：有n个处理器，给出n*n的邻接矩阵的一半，表示相互之间传输信息的花费（另一半与给出的一半对称，即双向都可传输），x表示不能传输，问从第一个处理器传输到所有处理器的最小花费总和是多少。
就是跑一遍最短路，然后求和……
原来我以前做的最短路都这么水……
1 #include<stdio.h>
2 #include<string.h>
3 #include<vector>
4 #include<algorithm>
5 #include<queue>
6 using namespace std;
7 typedef pair<int,int> pii;
8
9 struct cmp{
10 bool operator ()(pii a,pii b){
11 return a.first>b.first;
12 }
13 };
14
15 int g[105][105],dist[105],n;
16
17 int read(){
18 char c=getchar();
19 while(c!='x'&&(c>'9'||c<'0'))c=getchar();
20 if(c=='x')return 0x3f3f3f3f;
21 int d=0;
22 while(c>='0'&&c<='9'){
23 d*=10;
24 d+=c-'0';
25 c=getchar();
26 }
27 return d;
28 }
29
30 void dij(int s){
31 int i;
32 memset(dist,0x3f,sizeof(dist));
33 priority_queue<pii,vector<pii>,cmp>q;
34 dist[s]=0;
35 q.push(make_pair(dist[s],s));
36 while(!q.empty()){
37 pii u=q.top();
38 q.pop();
39 if(u.first>dist[u.second])continue;
40 for(i=1;i<=n;i++){
41 if(i!=u.second&&dist[i]>u.first+g[u.second][i]){
42 dist[i]=u.first+g[u.second][i];
43 q.push(make_pair(dist[i],i));
44 }
45 }
46 }
47 int ans=0;
48 for(i=1;i<=n;i++){
49 if(dist[i]>ans)ans=dist[i];
50 }
51 printf("%d
",ans);
52 }
53
54 int main(){
55 while(scanf("%d",&n)!=EOF){
56 memset(g,0x3f,sizeof(g));
57 int i,j;
58 for(i=2;i<=n;i++){
59 for(j=1;j<i;j++){
60 g[i][j]=g[j][i]=read();
61 }
62 }
63 dij(1);
64 }
65 return 0;
66 }