K20190407130211：新浪这么快开始面试了？？

justPassBy：dijskra， 时间相同时， 优先选蛋糕最多的。 #include <stdio.h> #include <string.h> #include <vector> #include <iostream> #include <queue> using namespace std; const int n = 10000 + 10; const int m = 2000000 + 10; typedef long long ll; ll a[n]; struct edge  { int v; int next; ll time; }e[m]; int head[n]; int cnt = 0; void add(int u, int v, int t) { e[cnt].v = v; e[cnt].time = t; e[cnt].next = head[u]; head[u] = cnt++; } ll times[n]; ll cakes[n]; struct node { int fa; int u; ll time; friend bool operator<(const node &a , const node &b)     {         return a.time>b.time;   // ascending sort     } }; priority_queue<node> q; void dij(int s, int d) { node cur; memset(cakes, 0, sizeof(cakes)); memset(times, -1, sizeof(times)); for(int i = head[s]; i != -1;  i = e[i].next) { node tmp; tmp.fa = s; tmp.u = e[i].v; tmp.time = e[i].time; q.push(tmp); } cakes[s] = a[s]; times[s] = 0; int i = 0; while(!q.empty()) { i+=1; cur = q.top(); q.pop(); //没有走过， 或者有更好的走法 if(times[cur.u] == -1 || cur.time < times[cur.u]) { times[cur.u] = cur.time; cakes[cur.u] = cakes[cur.fa] + a[cur.u]; } // 时间相同，选蛋糕更多的 else if(cur.time == times[cur.u]) { if(cakes[cur.fa] + a[cur.u] > cakes[cur.u]) cakes[cur.u] = cakes[cur.fa] + a[cur.u]; continue; } else { continue; } /* cout << cur.u << " " << cakes[cur.u] << endl; */ for(int i = head[cur.u]; i != -1; i = e[i].next) { if(times[e[i].v] != -1 && cur.time + e[i].time > times[e[i].v]) continue; node tmp; tmp.fa = cur.u; tmp.u = e[i].v; tmp.time = cur.time + e[i].time; q.push(tmp); } } cout << times[d] << " " << cakes[d] << endl; } int main() { int n, m, s, d; cin >> n >> m >> s >> d; s--; d--; for(int i = 0; i < n; ++i) { cin >> a[i]; } int u, v, t; memset(head, -1, sizeof(head)); for(int i = 0; i < m; ++i) { cin >> u >> v >> t; u--; v--; add(u, v, t); add(v, u, t); } dij(s, d); } //6 80

Coder小北：多面几次就好了