[关闭]
@Metralix 2018-03-08T22:25:23.000000Z 字数 7205 阅读 850

寒假训练 DIV1（3）最短路及其应用1

A - Airport Express

最短路

题目大意

某个人要从起点到终点， 有m个经济站和k个商业站， 只能乘坐一次商业站， 求最短时间。

解题思路

因为多了商业站， 所以不能直接套用最短路， 但是注意到只有一次乘坐商业站的机会， 所以直接枚举坐哪个商业站就行了， 这样，其他部分就是最短路了， 假设商业站是从a到b，花费c，那么答案就是d1[a] + d2[b] + c， d1是从起点的最短路，d2是从终点出发的最短路。

  1. #include<map>
  2. #include<queue>
  3. #include<stack>
  4. #include<cmath>
  5. #include<ctime>
  6. #include<cctype>
  7. #include<string>
  8. #include<cstdio>
  9. #include<cstring>
  10. #include<iostream>
  11. #include<algorithm>
  12. using namespace std;
  13. typedef long long ll;
  15. const int maxv = 500 + 5;
  16. const int max_dis = 999999999;
  17. struct Edge{
  18.     int to;
  19.     int dis;
  20.     Edge(int to,int dis){
  21.         this -> to = to;
  22.         this -> dis = dis;
  23.     }
  24. };
  26. int N,S,E,M,K;
  27. int X,Y,Z,cases=0;
  29. vector<Edge>G[maxv];
  30. int Sdis[maxv],Edis[maxv];
  31. int Shead[maxv],Ehead[maxv];
  32. int path[maxv],ans,Start,End,cnt;
  33. typedef pair<int,int>P;
  35. void init(){
  36.     Start=-1; cnt=0;
  37.     for(int i=0;i<maxv;i++) G[i].clear();
  38.     memset(Shead,-1,sizeof(Shead));
  39.     memset(Ehead,-1,sizeof(Ehead));
  40.     fill(Sdis+1,Sdis+1+N,max_dis);
  41.     fill(Edis+1,Edis+1+N,max_dis);
  42. }
  44. void dijkstra(int dis[],int head[],int s){
  45.     priority_queue<P,vector<P>,greater<P> >q;
  46.     while(!q.empty()) q.pop();
  47.     dis[s]=0;
  48.     q.push(P(0,s));
  49.     while(!q.empty()){
  50.         P p=q.top(); q.pop();
  51.         int v=p.second;
  52.         if(p.first>dis[v]) continue;
  53.         for(int i=0;i<G[v].size();i++){
  54.             Edge& e=G[v][i];
  55.             if(dis[v]+e.dis<dis[e.to]){
  56.                 head[e.to]=v;
  57.                 dis[e.to]=dis[v]+e.dis;
  58.                 q.push(P(dis[e.to],e.to));
  59.             }
  60.         }
  61.     }
  62. }
  64. void doit(){
  65.     dijkstra(Sdis,Shead,S);
  66.     dijkstra(Edis,Ehead,E);
  67.     ans=Sdis[E];
  68. }
  71. int main(){
  72.     while(scanf("%d%d%d",&N,&S,&E)!=EOF){
  73.         init();
  74.         scanf("%d",&M);
  75.         for(int i=0;i<M;i++){
  76.             scanf("%d%d%d",&X,&Y,&Z);
  77.             G[X].push_back(Edge(Y,Z));
  78.             G[Y].push_back(Edge(X,Z));
  79.         }
  80.         doit();
  81.         scanf("%d",&K);
  82.         for(int i=0;i<K;i++){
  83.             scanf("%d%d%d",&X,&Y,&Z);
  84.             if(Sdis[X]+Edis[Y]+Z<ans){
  85.                 Start=X; End=Y;
  86.                 ans=Sdis[X]+Edis[Y]+Z;
  87.             }
  88.             if(Sdis[Y]+Edis[X]+Z<ans){
  89.                 Start=Y; End=X;
  90.                 ans=Sdis[Y]+Edis[X]+Z;
  91.             }
  92.         }
  94.         if(cases) printf("\n");
  95.         cases++;
  96.         if(Start==-1){
  97.             for(int i=E;i!=-1;i=Shead[i]) path[cnt++]=i;
  98.             for(int i=cnt-1;i>=0;i--){
  99.                 if(i==0) printf("%d\n",path[i]);
  100.                 else printf("%d ",path[i]);
  101.             }
  102.             printf("Ticket Not Used\n%d\n",ans);
  103.         }
  104.         else{
  105.             for(int i=Start;i!=-1;i=Shead[i]) path[cnt++]=i;
  106.             reverse(path,path+cnt);
  107.             for(int i=End;i!=-1;i=Ehead[i]) path[cnt++]=i;
  108.             for(int i=0;i<cnt;i++){
  109.                 if(i==cnt-1) printf("%d\n",path[i]);
  110.                 else printf("%d ",path[i]);
  111.             }
  112.             printf("%d\n%d\n",Start,ans);
  113.         }
  114.     }return 0;
  115. }

B - Walk Through the Forest

标签： dijkstra

题目大意

只走（A,B）：存在一条从B出发回家的路，比所有从A出发回家的路径都短。问这样的路径有几条。

解题思路

先反向求一遍最短路，得到d数组。当d[B] < d[A]时，满足（A，B）路径，这样就能容易找到（A，B）路径，DFS找一遍总路径数就好了。

  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<iostream>
  4. using namespace std;
  5. #define MAXN 1005
  6. int cost[MAXN][MAXN];
  7. int dis[MAXN];
  8. int sum[MAXN];
  9. #define INF 0x3f3f3f3f  
  10. #define typec int  
  11. int path[MAXN],vis[MAXN];
  12. void Dijkstra(typec cost[][MAXN],typec lowcost[MAXN],int n,int beg)
  13. {
  14.     int i,j;
  15.     typec minc;
  16.     memset(vis,0,sizeof(vis));
  17.     vis[beg]=1;
  18.     for(i=1;i<=n;i++)
  19.     {
  20.         lowcost[i]=cost[beg][i];path[i]=beg;
  21.     }    
  22.     lowcost[beg]=0;
  23.     path[beg]=-1;//树根的标记
  24.     int pre;
  25.     for(int num=2;num<n;num++)
  26.     {
  27.         minc=INF;
  28.         for(j=1;j<=n;j++)
  29.            if(vis[j]==0&&lowcost[j]<minc)
  30.            {pre=j;minc=lowcost[j];}
  31.         if(minc>=INF)break;
  32.         vis[pre]=1;
  33.         for(j=1;j<=n;j++)
  34.           if(vis[j]==0&&lowcost[pre]+cost[pre][j]<lowcost[j])
  35.              {lowcost[j]=lowcost[pre]+cost[pre][j];path[j]=pre;}
  36.     }     
  37. }
  38. int dfs(int i,int n)
  39. {
  40.     if(i==2)  return 1;
  41.     if(sum[i]!=-1)  return sum[i];
  42.     int cnt=0;
  43.     for(int j=1;j<=n;j++)
  44.     {
  45.         if(cost[i][j]<INF&&dis[j]<dis[i])
  46.            cnt+=dfs(j,n);
  47.     }
  48.     sum[i]=cnt; 
  49.     return sum[i];   
  50. }    
  51. int main()
  52. {
  53.     int i,j;
  54.     int n,m;
  55.     int a,b,d;
  56.     while(scanf("%d",&n),n)
  57.     {
  58.         scanf("%d",&m);
  59.         for(i=1;i<=n;i++)
  60.            for(j=1;j<=n;j++)
  61.            {
  62.                if(i==j)cost[i][j]=0;
  63.                else cost[i][j]=INF;
  64.            } 
  65.         while(m--)
  66.         {
  67.             scanf("%d%d%d",&a,&b,&d);
  68.             cost[a][b]=d;
  69.             cost[b][a]=d;
  70.         }
  71.         Dijkstra(cost,dis,n,2);
  72.         memset(sum,-1,sizeof(sum));
  73.         printf("%d\n",dfs(1,n));
  75.     }    
  76. }

C - Warfare And Logistics

标签： 最短路

题目大意

 给出一个n节点m条边的无向图，每条边上有一个正权，令c等于每对结点的最短路径之和，要求删除一条边后使得新的c值最大，不连通的两个点距离视为L

解题思路

每次求单源最短路的同时记录下删除边的值，然后计算最小值就是了

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<queue>
  4. #include<vector>
  5. #include<algorithm>
  6. #define FOR(a,b,c) for(int a=(b);a<=(c);a++)
  7. using namespace std;
  9. const int maxn = 100+10,maxm=1000+10;
  10. const int INF=1e9;
  11. struct Edge{
  12.     int u,v,w,next;
  13. };
  15. int n,m,L;
  17. struct SPFA{
  18.     int n;
  19.     Edge e[2*maxm];
  20.     int en,front[maxn];
  21.     int inq[maxn],d[maxn];
  22.     int p[maxn];
  23.     queue<int> q;
  25.     void init(int n){
  26.         this->n=n;
  27.         en=-1;
  28.         memset(front,-1,sizeof(front));
  29.     }
  30.     void AddEdge(int u,int v,int w) {
  31.          en++; e[en].u=u; e[en].v=v; e[en].w=w; e[en].next=front[u]; front[u]=en;
  32.     }
  33.     void solve(int s) {
  34.         memset(inq,0,sizeof(inq));
  35.         memset(p,0,sizeof(p));
  36.         for(int i=1;i<=n;i++) d[i]=INF;
  38.         d[s]=0; inq[s]=1; q.push(s);
  39.         while(!q.empty()) {
  40.             int u=q.front(); q.pop(); inq[u]=0;
  41.             for(int i=front[u];i>=0;i=e[i].next) {
  42.                 int v=e[i].v,w=e[i].w;
  43.                 if(w>0 && d[v]>d[u]+w) {         
  44.                     d[v]=d[u]+w;
  45.                     p[v]=i;
  46.                     if(!inq[v]) {
  47.                         inq[v]=1;
  48.                         q.push(v);
  49.                     }
  50.                 }
  51.             }
  52.         }
  53.     }
  54. }spfa;
  56. vector<int> gr[maxn][maxn];  
  57. int idx[maxn][maxn];        
  58. int used[maxn][maxn][maxn];  
  59. int sum_single[maxn];       
  61. int CALC_C() {
  62.     int ans=0;
  63.     memset(used,0,sizeof(used));
  64.     FOR(scr,1,n) 
  65.     {
  66.         spfa.solve(scr);
  67.         sum_single[scr]=0;
  68.         FOR(v,1,n)
  69.         {
  70.            if(v!=scr) {
  71.                    int u=spfa.e[spfa.p[v]].u;
  72.                    used[scr][u][v]=used[scr][v][u]=1;
  73.            }
  74.            sum_single[scr] += spfa.d[v]==INF? L : spfa.d[v];
  75.         }
  76.         ans += sum_single[scr];
  77.     }
  78.     return ans;
  79. }
  80. int CALC_C2(int a,int b) {
  81.     int ans=0;
  82.     FOR(scr,1,n)
  83.     {
  84.           if(!used[scr][a][b]) ans+=sum_single[scr];  
  86.           else
  87.           {
  88.                 spfa.solve(scr);
  89.                 FOR(v,1,n) ans += spfa.d[v]==INF?L: spfa.d[v];
  90.           }
  91.     }
  92.     return ans;
  93. }
  95. int main() 
  96. {
  97.     while(scanf("%d%d%d",&n,&m,&L)==3) 
  98.     {
  99.         int u,v,w;
  100.         spfa.init(n);
  101.         FOR(i,1,n) FOR(j,1,n) gr[i][j].clear();
  102.         while(m--) {
  103.             scanf("%d%d%d",&u,&v,&w);
  104.             gr[u][v].push_back(w);
  105.             gr[v][u].push_back(w);
  106.         }
  107.         FOR(i,1,n) FOR(j,i+1,n) if(!gr[i][j].empty()){
  108.             sort(gr[i][j].begin(),gr[i][j].end());
  109.             spfa.AddEdge(i,j,gr[i][j][0]);
  110.             idx[i][j]=spfa.en;
  111.             spfa.AddEdge(j,i,gr[i][j][0]);
  112.             idx[j][i]=spfa.en;
  113.         }
  114.         int c=CALC_C(),c2=-1;
  115.         FOR(i,1,n) FOR(j,i+1,n) if(!gr[i][j].empty()){
  116.             int& e1=spfa.e[idx[i][j]].w;
  117.             int& e2=spfa.e[idx[j][i]].w;
  118.             if(gr[i][j].size()==1) e1=e2=-1;
  119.             else e1=e2=gr[i][j][1];         
  120.             c2=max(c2,CALC_C2(i,j));        
  121.             e1=e2=gr[i][j][0];
  122.         }
  123.         printf("%d %d\n",c,c2);
  124.     }
  125.     return 0;
  126. }

D - The Toll! Revisited

标签： dijstra

题目大意

  给定一个无向图，大写字母是城市，小写字母是村庄，经过城市交过路费为当前货物的%5，路过村庄固定交1，给定起点终点和到目标地点要剩下的货物，问最少要带多少货物上路，并输出路径，如果有多种方案，要求字典序最小

解题思路

 dijstra的逆向运用，d数组含义变成到该结点至少需要这么多货物，然后反向建图，从终点向起点反向做一遍

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <vector>
  4. #include <queue>
  5. #include <algorithm>
  7. using namespace std;
  8. typedef long long ll;
  9. const int maxn = 55;
  10. const int inf = 0x3f3f3f3f;
  12. int IDX(char ch) { if (ch >= 'A' && ch <= 'Z') return ch - 'A'; else return 26 + ch - 'a'; }
  13. char RIDX(int x) { if (x < 26) return 'A' + x; else return 'a' + x - 26; }
  15. int N = 52, M, S, E, L, V[maxn];
  16. ll D[maxn];
  17. vector<int> G[maxn], ans;
  19. struct State {
  20.     int u;
  21.     ll d;
  22.     State (int u = 0, ll d = 0): u(u), d(d) {}
  23.     bool operator < (const State& u) const { return d > u.d; }
  24. };
  26. void init () {
  27.     for (int i = 0; i <= N; i++) G[i].clear();
  29.     char s[5], e[5];
  30.     for (int i = 0; i < M; i++) {
  31.         scanf("%s%s", s, e);
  32.         int u = IDX(s[0]), v = IDX(e[0]);
  33.         G[u].push_back(v);
  34.         G[v].push_back(u);
  35.     }
  36.     scanf("%d%s%s", &L, s, e);
  37.     S = IDX(s[0]), E = IDX(e[0]);
  38. }
  40. ll limit (int x, ll w) {
  41.     if (x >= 26) return w+1;
  42.     ll l = 0, r = inf;
  43.     while (l < r) {
  44.         ll mid = (l + r) >> 1;
  45.         ll t = mid + w;
  46.         if (t - (t + 19) / 20 >= w) r = mid;
  47.         else l = mid + 1;
  48.     }
  49.     return w + l;
  50. }
  52. ll consume(int u, ll d) {
  53.     if (u >= 26) return 1;
  54.     else return (d + 19) / 20;
  55. }
  57. void put (int u) {
  58.     ans.push_back(u);
  59.     if (u == E) return;
  61.     int rec = -1;
  62.     for (int i = 0; i < G[u].size(); i++) {
  63.         int v = G[u][i];
  64.         if (D[u] - consume(v, D[u]) == D[v] && (rec == -1 || rec > v))
  65.             rec = v;
  66.     }
  67.     put(rec);
  68. }
  70. void dijkstra () {
  71.     memset(V, 0, sizeof(V));
  72.     memset(D, inf, sizeof(D));
  74.     D[E] = L;
  76.     priority_queue<State> Q;
  77.     Q.push(State(E, D[E]));
  79.     while (!Q.empty()) {
  80.         int u = Q.top().u;
  81.         Q.pop();
  83.         if (V[u]) continue;
  84.         V[u] = 1;
  85.         ll w = limit(u, D[u]);
  87.         for (int i = 0; i < G[u].size(); i++) {
  88.             int v = G[u][i];
  89.             if (D[v] > w) {
  90.                 D[v] = w;
  91.                 Q.push(State(v, w));
  92.             }
  93.         }
  94.     }
  96.     printf("%lld\n", D[S]);
  97.     ans.clear();
  98.     put(S);
  99.     for (int i = 0; i < ans.size(); i++) {
  100.         printf("%c%c", RIDX(ans[i]), i == ans.size()-1 ? '\n' : '-');
  101.     }
  102. }
  104. int main () {
  105.     int cas = 1;
  106.     while (scanf("%d", &M) == 1 && M != -1) {
  107.         init ();
  108.         printf("Case %d:\n", cas++);
  109.         dijkstra();
  110.     }
  111.     return 0;
  112. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注