1003：
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=550;
6 const int INF=0x3f3f3f3f;
7 int g[N][N];
8 bool vis[N];
9 int dis[N];
10 int n,m;
11 int s,t;
12 int w[N];
13 int va[N];
14 int num[N];
15 void init()
16 {
17 for(int i=0;i<N;i++)
18 {
19 for(int j=0;j<N;j++)
20 {
21 g[i][j]=INF;
22 }
23 }
24 }
25 void dijkstra(int s)
26 {
27 memset(dis,INF,sizeof(dis));
28 dis[s]=0;
29 num[s]=1;
30 va[s]=w[s];
31 for(int i=0;i<n;i++)
32 {
33 int u=-1;
34 int Min=INF;
35 for(int j=0;j<n;j++)
36 {
37 if(!vis[j]&&dis[j]<Min)
38 {
39 u=j;
40 Min=dis[j];
41 }
42 }
43 // if(u==-1)
44 // return ;
45 vis[u]=true;
46 for(int v=0;v<n;v++)
47 {
48 if(!vis[v]&&g[u][v]!=INF)
49 {
50 if(dis[u]+g[u][v]<dis[v])
51 {
52 //vis[v]=true;
53 dis[v]=dis[u]+g[u][v];
54 num[v]=num[u];
55 va[v]=va[u]+w[v];
56 }
57
58 else if(dis[u]+g[u][v]==dis[v])
59 {
60 if(va[u]+w[v]>va[v])
61 {
62 va[v]=va[u]+w[v];
63 }
64 num[v]+=num[u];
65 }
66 }
67 }
68 }
69 }
70 signed main()
71 {
72 IOS;
73 init();
74 cin>>n>>m>>s>>t;
75 for(int i=0;i<n;i++)
76 {
77 cin>>w[i];
78 }
79 int st,f,d;
80 for(int i=0;i<m;i++)
81 {
82 cin>>st>>f>>d;
83 g[st][f]=g[f][st]=d;
84 }
85 dijkstra(s);
86 cout<<num[t]<<" "<<va[t];
87 return 0;
88 }
1030
dfs版本
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=550;
6 const int INF=0x3f3f3f3f;
7 int n,m,s,d;
8 int g[N][N];
9 int dis[N];
10 bool vis[N];
11 int cost[N][N];
12 int w[N];
13 vector<int>pre[N];
14 vector<int>tmp,path;
15 int ans=INF;
16 void init()
17 {
18 for(int i=0;i<N;i++)
19 {
20 for(int j=0;j<N;j++)
21 {
22 g[i][j]=INF;
23 cost[i][j]=INF;
24 }
25 }
26 }
27 void dfs(int p)
28 {
29 if(p==s)
30 {
31 tmp.push_back(p);
32 int value=0;
33 for(int i=tmp.size()-1;i>0;i--)
34 {
35 int id1=tmp[i];
36 int id2=tmp[i-1];
37 value+=cost[id1][id2];
38 }
39 if(value<ans)
40 {
41 ans=value;
42 path=tmp;
43 }
44 tmp.pop_back();
45 return ;
46 }
47 tmp.push_back(p);
48 for(int i=0;i<pre[p].size();i++)
49 {
50 dfs(pre[p][i]);
51 }
52 tmp.pop_back();
53 }
54 void dijkstra()
55 {
56 memset(dis,INF,sizeof(dis));
57 dis[s]=0;
58 w[s]=0;
59 for(int i=0;i<n;i++)
60 {
61 int u=-1;
62 int minn=INF;
63 for(int j=0;j<n;j++)
64 {
65 if(!vis[j]&&dis[j]<minn)
66 {
67 u=j;
68 minn=dis[j];
69 }
70 }
71 if(u==-1)
72 return ;
73 vis[u]=true;
74 for(int v=0;v<n;v++)
75 {
76 if(!vis[v]&&g[u][v]!=INF)
77 {
78 if(dis[u]+g[u][v]<dis[v])
79 {
80 dis[v]=dis[u]+g[u][v];
81 pre[v].clear();
82 pre[v].push_back(u);
83 }
84 else if(dis[u]+g[u][v]==dis[v])
85 {
86 pre[v].push_back(u);
87 }
88 }
89 }
90 }
91 }
92 signed main()
93 {
94 IOS;
95 cin>>n>>m>>s>>d;
96 init();
97 int st,ed,d1,c1;
98 for(int i=0;i<m;i++)
99 {
100 cin>>st>>ed>>d1>>c1;
101 g[st][ed]=g[ed][st]=d1;
102 cost[st][ed]=cost[ed][st]=c1;
103 }
104 dijkstra();
105 dfs(d);
106 for(int i=path.size()-1;i>=0;i--)
107 {
108 cout<<path[i]<<" ";
109 }
110 cout<<dis[d]<<" "<<ans;
111 return 0;
112 }
dijkstra+dfs版本
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=510;
6 const int INF=0x3f3f3f3f;
7 int n,m,s,t;
8 int g[N][N];
9 int cost[N][N];
10 int dis[N];
11 int ans=INF;
12 bool vis[N];
13 vector<int>path,tmp;
14 vector<int>pre[N];
15 void init()
16 {
17
18 for(int i=0;i<N;i++)
19 {
20 for(int j=0;j<N;j++)
21 {
22 g[i][j]=INF;
23 cost[i][j]=INF;
24 }
25 }
26 }
27 void dijkstra()
28 {
29 for(int i=0;i<N;i++)
30 {
31 dis[i]=INF;
32 }
33 dis[s]=0;
34 for(int i=0;i<n;i++)
35 {
36 int u=-1;
37 int minn=INF;
38 for(int j=0;j<n;j++)
39 {
40 if(!vis[j]&&dis[j]<minn)
41 {
42 u=j;
43 minn=dis[j];
44 }
45 }
46 if(u==-1)
47 return ;
48 vis[u]=true;
49 for(int v=0;v<n;v++)
50 {
51 if(!vis[v]&&g[u][v]!=INF)
52 {
53 if(dis[u]+g[u][v]<dis[v])
54 {
55 dis[v]=dis[u]+g[u][v];
56 pre[v].clear();
57 pre[v].push_back(u);
58 }
59 else if(dis[u]+g[u][v]==dis[v])
60 {
61 //pre[v].push_back(u);
62 pre[v].push_back(u);
63
64 }
65 }
66 }
67 }
68 }
69 void dfs(int p)
70 {
71 if(p==s)
72 {
73 tmp.push_back(p);
74 int value=0;
75 for(int i=tmp.size()-1;i>0;i--)
76 {
77 int id1=tmp[i];
78 int id2=tmp[i-1];
79 value+=cost[id1][id2];
80 }
81 if(value<ans)
82 {
83 ans=value;
84 path=tmp;
85 }
86 tmp.pop_back();
87 return ;
88 }
89 tmp.push_back(p);
90 for(int i=0;i<pre[p].size();i++)
91 {
92 dfs(pre[p][i]);
93 }
94 tmp.pop_back();
95 }
96 signed main()
97 {
98 IOS;
99 init();
100 cin>>n>>m>>s>>t;
101 for(int i=0;i<m;i++)
102 {
103 int u,v,d,w;
104 cin>>u>>v>>d>>w;
105 g[u][v]=g[v][u]=d;
106 cost[u][v]=cost[v][u]=w;
107 }
108 dijkstra();
109 dfs(t);
110 for(int i=path.size()-1;i>=0;i--)
111 {
112 cout<<path[i]<<" ";
113 }
114 cout<<dis[t]<<" "<<ans;
115 return 0;
116 }
1087：
1 #include <iostream>
2 #include <map>
3 #include <vector>
4 #include <algorithm>
5 using namespace std;
6 int n, k;
7 const int inf = 999999999;
8 int e[205][205], weight[205], dis[205];
9 bool visit[205];
10 vector<int> pre[205], temppath, path;
11 map<string, int> m;
12 map<int, string> m2;
13 int maxvalue = 0, mindepth, cntpath = 0;
14 double maxavg;
15 void dfs(int v) {
16 temppath.push_back(v);
17 if(v == 1) {
18 int value = 0;
19 for(int i = 0; i < temppath.size(); i++) {
20 value += weight[temppath[i]];
21 }
22 double tempavg = 1.0 * value / (temppath.size() - 1);
23 if(value > maxvalue) {
24 maxvalue = value;
25 maxavg = tempavg;
26 path = temppath;
27 } else if(value == maxvalue && tempavg > maxavg) {
28 maxavg = tempavg;
29 path = temppath;
30 }
31 temppath.pop_back();
32 cntpath++;
33 return ;
34 }
35 /* for(int i = 0; i < pre[v].size(); i++) {
36 dfs(pre[v][i]);
37 }*/
38 for(int i=pre[v].size()-1;i>=0;i--)
39 {
40 dfs(pre[v][i]);
41 }
42 temppath.pop_back();
43 }
44 int main() {
45 fill(e[0], e[0] + 205 * 205, inf);
46 fill(dis, dis + 205, inf);
47 scanf("%d %d", &n, &k);
48 string s;
49 cin >> s;
50 m[s] = 1;
51 m2[1] = s;
52 for(int i = 1; i < n; i++) {
53 cin >> s >> weight[i+1];
54 m[s] = i+1;
55 m2[i+1] = s;
56 }
57 string sa, sb;
58 int temp;
59 for(int i = 0; i < k; i++) {
60 cin >> sa >> sb >> temp;
61 e[m[sa]][m[sb]] = temp;
62 e[m[sb]][m[sa]] = temp;
63 }
64 dis[1] = 0;
65 for(int i = 0; i < n; i++) {
66 int u = -1, minn = inf;
67 for(int j = 1; j <= n; j++) {
68 if(visit[j] == false && dis[j] < minn) {
69 u = j;
70 minn = dis[j];
71 }
72 }
73 if(u == -1) break;
74 visit[u] = true;
75 for(int v = 1; v <= n; v++) {
76 if(visit[v] == false && e[u][v] != inf) {
77 if(dis[u] + e[u][v] < dis[v]) {
78 dis[v] = dis[u] + e[u][v];
79 pre[v].clear();
80 pre[v].push_back(u);
81 } else if(dis[v] == dis[u] + e[u][v]) {
82 pre[v].push_back(u);
83 }
84 }
85 }
86 }
87 int rom = m["ROM"];
88 dfs(rom);
89 printf("%d %d %d %d\n", cntpath, dis[rom], maxvalue, (int)maxavg);
90 for(int i = path.size() - 1; i >= 1; i--) {
91 cout << m2[path[i]] << "->";
92 }
93 cout << "ROM";
94 return 0;
95 }
1072：
1 #include<iostream>
2 #include<string>
3 #include<vector>
4 #include<algorithm>
5 #define INF (~(0x1<<31))
6 using namespace std;
7 int gra[1100][1100];
8 int n, m, k, ds, mind = 0,minnode = -1;
9 double average = INF;
10 vector<int> distd;
11 int toint(string s) {
12 int ans=0;
13 if(s[0]=='G')
14 {
15 for(int i=1;i<s.length();i++)
16 {
17 ans=ans*10+(s[i]-'0');
18 }
19 ans=ans+n;
20 }
21 else
22 {
23 for(int i=0;i<s.length();i++)
24 {
25 ans=ans*10+(s[i]-'0');
26 }
27 }
28 return ans;
29 }
30 void dijsktra(int v) {
31 vector<bool> visit(1100);
32 vector<int> dist(1100, INF);
33 dist[v] = 0;
34 for (int i = 0; i < n + m; i++) {//执行n+m次
35 int min = INF, u = -1;
36 for (int j = 1; j <= n + m; j++) {
37 if (!visit[j] && dist[j] < min) {
38 u = j;
39 min = dist[j];
40 }
41 }
42 if (u == -1) break;
43 visit[u] = true;
44 for (int j = 1; j <= n + m; j++) {//更新
45 if (!visit[j] && gra[u][j] != INF) {
46 if (dist[u] + gra[u][j] < dist[j])
47 dist[j] = dist[u] + gra[u][j];
48 }
49 }
50 }
51 int min = INF;
52 double sum = 0;
53 for (int i = 1; i <= n; i++) {//找最小节点
54 if (dist[i] < min) {
55 min = dist[i];
56 sum += 1.0*dist[i];
57 }
58 if (dist[i] > ds) return;//说明该加油站不能覆盖所有住户
59 }
60 if ((min > mind) || (min == mind && sum/n < average)) {
61 mind = min;
62 minnode = v;
63 average = sum / n;
64 distd = dist;
65 }
66 return;
67 }
68 int main() {
69 scanf("%d %d %d %d", &n, &m, &k, &ds);
70 fill(gra[0] , gra[0] + 1100 * 1100, INF);
71 for (int i = 0; i < k; i++) {
72 string s1,s2;
73 int d;
74 cin >> s1 >> s2 >> d;
75 int a = toint(s1);
76 int b = toint(s2);
77 gra[a][b] = gra[b][a] = d;
78 }
79 for (int i = n + 1; i <= n + m; i++) //从G1出发找最短路径
80 dijsktra(i);
81 if (minnode == -1) {
82 cout << "No Solution";
83 return 0;
84 }
85 cout << "G" << minnode - n << endl;
86 int sum = 0;
87 for (int i = 1; i <= n; i++)
88 sum += distd[i];
89 printf("%.1f %.1f", (double)mind,(double)sum/n);
90 return 0;
91 }
标签：pat,int,value,st,dijkstra,详解,temppath,INF,include From： https://www.cnblogs.com/LQS-blog/p/16922242.html