题目

解决

思路

Dijkstra+DFS实现，也可以直接Dijstra实现

实现

Code1

#include<cstdio> #include<algorithm> #include<cstring> #include<vector> using namespace std; const int N = 510; const int INF = 1000000000; int n, m, st, ed; int G[N][N]; //图 int weight[N]; //点权 bool vis[N] = {false}; int d[N]; //最短距离 int optvalue; //第二标尺最优值 int num = 0; //最短路径条数 vector<int> pre[N]; //路径：存放结点的前驱结点 vector<int> path, tempPath; //最优路径,临时路径 void DFS(int v){ if(v == st){ //路径起点 num++; tempPath.push_back(v); int value = 0; for(int i=tempPath.size()-1; i>=0; i--){ int id = tempPath[i]; value += weight[id]; } if(value > optvalue){ optvalue = value; path = tempPath; } tempPath.pop_back(); //将刚加入的结点删除 return; } tempPath.push_back(v); for(int i=0; i<pre[v].size(); i++){ DFS(pre[v][i]); //结点v的前驱结点 } tempPath.pop_back(); //遍历完所有前驱结点，将当前结点v删除 } void Dijkstra(int s){ fill(d, d+N, INF); //初始化距离 d[s] = 0; for(int i=0; i<n; i++){ int u = -1; int MIN = INF; for(int j=0; j<n; j++){ if(vis[j] == false && d[j] < MIN){ u = j; MIN = d[j]; } } if(u == -1) return; vis[u] = true; for(int v=0; v<n; v++){ if(vis[v] == false && G[u][v] != INF){ if(d[u]+G[u][v] < d[v]){ d[v] = d[u] + G[u][v]; //优化d[v] pre[v].clear(); //清空pre[v] pre[v].push_back(u); //令v的前驱是u }else if(d[u]+G[u][v] == d[v]){ pre[v].push_back(u); //令v的前驱是u } } } } } int main(){ scanf("%d%d%d%d", &n, &m, &st, &ed); for(int i=0; i<n; i++){ scanf("%d", &weight[i]); } fill(G[0], G[0]+N*N, INF); //初始化图G int a, b, dis; for(int i=0; i<m; i++){ scanf("%d%d%d", &a, &b, &dis); G[a][b] = dis; G[b][a] = dis; } Dijkstra(st); DFS(ed); printf("%d %d", num, optvalue); return 0; }