pta 1003

https://pintia.cn/problem-sets/994805342720868352/problems/994805523835109376

朴素dijkstra+pre记录前驱+dfs输出前驱

朴素dijkstra，升级版是天梯赛l2-1紧急救援

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define int long long
  4 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  5 const int N=5e2+10;
  6 const int INF=0x3f3f3f3f;
  7 int g[N][N];
  8 int p[N];
  9 bool vis[N];
 10 int w[N];
 11 int num[N];
 12 int n,m;
 13 int s,t;
 14 int dis[N];
 15 void dijkstra()
 16 {
 17     for(int i=0;i<N;i++)
 18     {
 19         dis[i]=INF;
 20         w[i]=0;
 21         num[i]=0;
 22     }
 23     dis[s]=0;
 24     num[s]=1;
 25     w[s]=p[s];
 26     for(int i=0;i<n;i++)
 27     {
 28         int u=-1;
 29         int minn=INF;
 30         for(int j=0;j<n;j++)
 31         {
 32             if(!vis[j]&&dis[j]<minn)
 33             {
 34                 u=j;
 35                 minn=dis[j];
 36             }
 37         }
 38         vis[u]=true;
 39         for(int v=0;v<n;v++)
 40         {
 41             /*if(!vis[v]&&g[u][v]!=INF)
 42             {
 43                 if(dis[u]+g[u][v]<dis[v])
 44                 {
 45                     dis[v]=dis[u]+g[u][v];
 46                     num[v]=num[u];
 47                     w[v]=w[u]+p[v];
 48                 }
 49                 else if(dis[u]+g[u][v]==dis[v])
 50                 {
 51                     if(w[u]+p[v]>w[v])
 52                     {
 53                         w[v]=w[u]+p[v];
 54                     }
 55                     num[v]+=num[u];
 56                 }
 57             }*/
 58             if(!vis[v]&&!g[u][v]!=INF)
 59             {
 60                 if(dis[u]+g[u][v]<dis[v])
 61                 {
 62                     dis[v]=dis[u]+g[u][v];
 63                     num[v]=num[u];
 64                     w[v]=w[u]+p[v];
 65                 }
 66                 else if(dis[u]+g[u][v]==dis[v])
 67                 {
 68                     if(w[u]+p[v]>w[v])
 69                     {
 70                         w[v]=p[v]+w[u];
 71                     }
 72                     num[v]+=num[u];
 73                 }
 74             }
 75         }
 76     }
 77 }
 78 signed main()
 79 {
 80     IOS;
 81     cin>>n>>m>>s>>t;
 82     for(int i=0;i<n;i++)
 83     {
 84         cin>>p[i];
 85     }
 86     for(int i=0;i<N;i++)
 87     {
 88         for(int j=0;j<N;j++)
 89         {
 90             g[i][j]=INF;
 91         }
 92     }
 93     for(int i=0;i<m;i++)
 94     {
 95         int u,v,w;
 96         cin>>u>>v>>w;
 97         g[u][v]=w;
 98         g[v][u]=w;
 99     }
100     dijkstra();
101     cout<<num[t]<<" "<<w[t];
102     return 0;
103 }