2019百度之星第三场 最短路2

思路：

用dijkstra算法计算最短路的过程中同时保存路径中最大的节点编号。

实现：

 1 #include
 2 using namespace std;
 3 const int mod=998244353;
 4 int work(int s,vectorint,int>>>&a){
 5     using pli=pair<long long,int>;
 6     priority_queue,greater>q;
 7     long long INF=0x3f3f3f3f3f3f3f3f;
 8     int n=a.size();
 9     vector<long long>dis(n,INF);
10     dis[s]=0;
11     vector<int>pre(n,0);
12     q.push({0ll,s});
13     while(!q.empty()){
14         auto tmp=q.top();q.pop();
15         long long d=tmp.first;
16         int id=tmp.second;
17         if(d>dis[id])continue;
18         for(int i=0;i){
19             int to=a[id][i].first,cost=a[id][i].second;
20             long long new_d=d+cost;
21             if(new_d<dis[to]){
22                 dis[to]=new_d;
23                 q.push({new_d,to});
24                 if(id!=s){
25                     pre[to]=max(pre[id],id);
26                 }
27             }
28             else if(new_d==dis[to]){
29                 if(id!=s){
30                     pre[to]=min(pre[to],max(pre[id],id));
31                 }
32             }
33         }
34     }
35     int res=0;
36     for(int i=1;i){
37         res=(res+pre[i])%mod;
38     }
39     return res;
40 }
41 int main(){
42     ios::sync_with_stdio(false);
43     int t;cin>>t;
44     while(t--){
45         int n,m;
46         cin>>n>>m;
47         vectorint,int>>>g(n+1,vectorint,int>>());
48         for(int i=0;i){
49             int a,b,w;
50             cin>>a>>b>>w;
51             g[a].push_back({b,w});
52             g[b].push_back({a,w});
53         }
54         int res=0;
55         for(int i=1;i<=n;i++){
56             int tmp=work(i,g);
57             res=(res+tmp)%mod;
58         }
59         cout<endl;
60     }
61     return 0;
62 }