题目链接 随着刷题的进行， 越来越趋向于用套路来写， 而不是靠思考， 例如本题， 就适合用Dijkstra+sort来写。 套路如下：
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int maxV=1100; const int INF=1000000000; int n,m,k,ds; int G[maxV][maxV],d[maxV]; bool vis[maxV]={false}; struct Node{ double minDis, avg; int isOK,id; Node(){ isOK=1; minDis=INF; avg=0; } }node[20]; bool cmp(Node a, Node b){ if (a.isOK!=b.isOK) return a.isOK>b.isOK; else if (a.minDis!=b.minDis) return a.minDis>b.minDis; else if (a.avg!=b.avg) return a.avg<b.avg; else return a.id<b.id; } void Dijkstra(int s){ fill(d, d+maxV, INF); fill(vis, vis+maxV, false); d[s]=0; for (int i=0; i<n+m; i++){ int u=-1, min=INF; for (int j=1; j<=n+m; j++){ if (!vis[j] && d[j]<min){ u=j; min=d[j]; } } if (u==-1) return; vis[u]=true; for (int v=1; v<=n+m; v++){ if (!vis[v] && G[u][v]!=INF){ if (d[u]+G[u][v]<d[v]){ d[v]=d[u]+G[u][v]; } } } } } int getID(char str[]){ int len=strlen(str); int ans=0; if (str[0]=='G'){ for (int i=1; i<len; i++){ ans=ans*10+(str[i]-'0'); } return n+ans; }else { for (int i=0; i<len; i++){ ans=ans*10+(str[i]-'0'); } return ans; } } int main(){ scanf("%d %d %d %d",&n, &m, &k, &ds); fill(G[0], G[0]+maxV*maxV, INF); for (int i=0; i<k; i++){ char str1[10], str2[10]; scanf("%s %s", str1, str2); int u=getID(str1); int v=getID(str2); scanf("%d",&G[u][v]); G[v][u]=G[u][v]; } for (int i=n+1; i<=n+m; i++){ Dijkstra(i); node[i-n].id=i-n; for (int j=1; j<=n; j++){ if (d[j]>ds){ node[i-n].isOK=0; break; } if (d[j]<node[i-n].minDis){ node[i-n].minDis=d[j]; } node[i-n].avg+=1.0*d[j]/n; } } sort(node+1, node+m+1, cmp); if (node[1].isOK==0) printf("No Solution"); else { printf("G%d\n",node[1].id); printf("%.1f %.1f", node[1].minDis, node[1].avg); } }《算法笔记》上面没用sort, 这样会变得很麻烦， 思路不够清楚的话， 容易出错， 而且《算法笔记》上的答案并没有对 index 进行比较， 不过也能通过所有测试， 这是因为题目中虽然说当所有条件都相同时， 输出Index小的那一个， 但实际上测试点中没有这种情况。
