PY学长的放毒题
Description
下面开始PY的香港之行，PY有n个要去的小吃店，这n个小吃店被m条路径联通起来。
PY有1个传送石和n−1个传送石碎片。
PY可以用传送石标记一个小吃店作为根据地。
每当PY吃完一个地点的美食，必须回到根据地（传送石标记的小吃店）休息一段时间，才能去另外一个小吃店。
也就是说你从根据地走去另一个小吃店吃完之后，不需要再走回来，用传送石碎片即可回来。
现在PY想知道他该标记那个小吃店才能让她走最短的路程吃完这n个小吃店？
请聪明的你思考上述问题，并告诉他所需走的路程总和 和 他该标记那个地点作为根据地。
ps.传送石只能标记一个小吃店。
Input
本题需要多组输入（lazy
第一行两个整数n,m,表示n家小吃店,有m条路径1<=n<=1000,1<=m<=10000)
接下来m行，每行3个整数u,v,w, 表示第u家小吃店到第v家小吃店有一条长度为w米的路径。(0<=w<=4e5)，数据保证u!=v。
Output
输出两个整数 PY需要最少走多远才能吃完这n个小吃店的距离 和 被传送石标记的小吃店的标号。
如果距离相同，输出标号最小的。保证至少存在一个解
该题为最短路裸题，只需对图上n个点进行n次dijkstra即可
（注意要用优先队列 + 前向星 的dijkstra
ACODE:
//7777777 #include<stdio.h> #include<iostream> #include<string.h> #include<algorithm> #include<math.h> #include<string> #include<queue> #include<utility> #include<vector> #define lson l , m , rt << 1 #define rson m+1 , r , rt << 1 | 1 #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; typedef long long ll; const double pi = 3.1415926535; const double eps = 1e-6; const int MXN = 1e3 + 7; const int MXM = 1e4 + 7; const int maxbit = 18; const double val = pi/180.0; const int INF = 0x3f3f3f3f; const ll LINF = 0x3f3f3f3f3f3f3f3f; int n,m; int head[MXN],dis[MXN]; int cnt; struct Edge { int u,v,w,next; }e[MXM<<1]; struct node { int w,now; inline bool operator <(const node &x)const { return w > x.w; } }; priority_queue<node>q; inline void add(int u,int v,int w) { e[cnt++].u = u; e[cnt].v = v; e[cnt].w = w; e[cnt].next = head[u]; head[u] = cnt; } void dijkstra(int S) { for(int i = 1;i <= n;++i) { dis[i] = INF; } dis[S] = 0; q.push((node){0,S}); while(!q.empty()) { node x = q.top(); q.pop(); int u = x.now; for(int i = head[u];i;i = e[i].next) { int v = e[i].v; if(dis[v] > dis[u] + e[i].w) { dis[v] = dis[u] + e[i].w; q.push((node){dis[v],v}); } } } } void init() { mem(head,0); mem(e,0); mem(dis,0); cnt = 0; } int main(int argc, char const *argv[]) { while(~scanf("%d%d",&n,&m)) { ll cont = 0; ll ans = INF; int p; init(); for(int i = 1;i <= m;++i) { int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,w); } for(int i = 1;i <= n;++i) { cont = 0; mem(dis,0); dijkstra(i); for(int j = 1;j <= n;++j) { cont +=dis[j]; } //printf("%d\n",cont); if(cont < ans) { ans = cont; p = i; } } printf("%lld %d\n",ans,p); } }