Description
PY利用寒假摸鱼时间去了一趟香港吃吃吃，下面就由我介绍一下我遇到的好吃的香港美食。
首先介绍第一家合益泰小食，这家主打肠粉，这家的肠粉特别的正宗，价格非常亲民，口感非常好
公和荳品厂，这家的豆腐花特别好吃，超级嫩，口感又香又滑。
添好运——这是一家港式点心店，我推荐吃这里的糯米鸡和凤爪，口感都非常好，这里的虾饺也很好吃。
不过叉烧包太甜了，甜到我受不了了。
最后推荐一个华星冰室，不能多写了，不然题面写不下了。这里我极力推荐这家店的奶茶，
奶和茶混合的刚刚好的样子，没有以前我喝的以前的奶茶的那种过分甜，一点茶的味道都没有。（喝过很多奶茶，一个个都甜的不得了）
aaaaa.pngbbbbbbbbbbbbbbbb.pngcccccccccccccc.pngddddddddddddddd.pngeeeeeeeeeeeeeeeeeeeeee.png
下面开始PY的香港之行，PY有nn个要去的小吃店，这nn个小吃店被mm条路径联通起来。
PY有11个传送石和n-1n−1个传送石碎片。
PY可以用传送石标记一个小吃店作为根据地。
每当PY吃完一个地点的美食，必须回到根据地（传送石标记的小吃店）休息一段时间，才能去另外一个小吃店。
也就是说你从根据地走去另一个小吃店吃完之后，不需要再走回来，用传送石碎片即可回来。
现在PY想知道他该标记那个小吃店才能让她走最短的路程吃完这nn个小吃店？
请聪明的你思考上述问题，并告诉他所需走的路程总和 和 他该标记那个地点作为根据地。
ps.传送石只能标记一个小吃店。
思路：最短路枚举求和，我一开始用vector邻接表诡异超时，后来改用前向星才过了，莫非是OJ卡vector??
#include#include #include #include #include using namespace std; #define MAXM 10010#define MAXN 10010#define INF 1e9struct Edge{ long long to; //这条边的终点 long long next; //下一条边的存储下标 long long w; //权值}edge[MAXM * 2]; struct node{ long long u,dis; node(long long u,long long dis):u(u),dis(dis){ } bool operator < (const node& rhs)const { return dis > rhs.dis; }};long long dis[MAXN];long long n, m, cnt; long long head[MAXN]; long long vis[MAXN] ;void Add(long long u, long long v, long long w) { edge[cnt].w = w; edge[cnt].to = v; edge[cnt].next = head[u]; head[u] = cnt++; } long long dijkstra(long long s, long long n) { priority_queue q; q.push(node( s,0 )); for(long long i = 1;i<=n;i++) dis[i] = INF; dis[s] = 0; memset(vis,0,sizeof(vis)); while (!q.empty()) { node now = q.top(); q.pop(); long long u = now.u; long long d = now.dis; if(vis[u]) continue; vis[u] = 1; for (long long i = head[u]; ~i; i = edge[i].next) { long long t = edge[i].to, v = edge[i].w; if (!vis[t]&&dis[t] > dis[u] + v) { dis[t] = dis[u] + v; q.push(node( t,dis[t] )); } } } long long ans = 0; for (long long i = 1; i <= n; i++) ans += dis[i]; return ans;// return dis[n];}int main() { long long u, v, w; while(~scanf("%lld%lld",&n,&m)) { cnt = 0; memset(head,-1,sizeof(head)); for(long long i=1; i<=m; i++) { scanf("%lld%lld%lld",&u,&v,&w); Add(u, v, w); Add(v, u, w); } long long a,b; long long min_p,min_d; min_p = 0,min_d = INF; for(long long i = 1;i<=n;i++) { long long ans = dijkstra(i,n); if(min_d>ans) { min_d = ans; min_p = i; } } printf("%lld %lld\n",min_d,min_p); } return 0;}