L3-007 天梯地图 (30分) 最短路+dp

最短路+dp思路：nuoyanli 520 Let‘s play computer game

输入样例1：

输出样例1：

Time = 6: 5 => 4 => 8 => 3
Distance = 3: 5 => 1 => 3

输入样例2：

输出样例2：

Time = 3; Distance = 4: 3 => 2 => 5

这个nuoyanli 520 Let‘s play computer game 就是讲最短路+dp思路的，它可以满足例如这样的条件 “最快到达路线不唯一，则输出几条最快路线中最短的那条”

这样的话我们就可以采用两边最短路+dp就可以了

代码：

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<algorithm>
  7 #include<queue>
  8 using namespace std;
  9 typedef long long ll;
 10 typedef unsigned long long ull;
 11 const int MAXN=1000000;
 12 const int MIN_INF=0x80000000;
 13 const int MAX_INF=0x7fffffff;
 14 int n,m;
 15 int beg[505];
 16 int to[505050];
 17 int nex[505050];
 18 int weight[505050];
 19 int tisme[505050];
 20 int e;
 21 int st,ed;
 22 bool vis[505];
 23 int answ[505];
 24 int anst[505];
 25 int stepw[505];
 26 int tarw[505];
 27 int tart[505];
 28 int answw[505];
 29 int answwsize;
 30 int anstt[505];
 31 int ansttsize;
 32 
 33 struct p{
 34     int val;
 35     int self;
 36     int step;
 37     bool operator <(const p &b)const{
 38         return val>b.val;
 39     }
 40 };
 41 
 42 
 43 priority_queue<p> q;
 44 void init(){
 45     e=0;
 46     memset(beg,-1,sizeof(beg));
 47 //    answw="";
 48 //    anstt="";
 49     return;
 50 }
 51 //Function area
 52 
 53 void add(int a,int b,int w,int t){
 54     nex[++e]=beg[a];
 55     beg[a]=e;
 56     to[e]=b;
 57     weight[e]=w;
 58     tisme[e]=t;
 59 }
 60 
 61 void Dijkstraw(int start){
 62     q.push({0,start,0});
 63     memset(vis,0,sizeof(vis));
 64     memset(answ,0x3f3f3f3f,sizeof(answ));
 65     memset(tarw,-1,sizeof(tarw));
 66     memset(stepw,0x3f3f3f3f,sizeof(stepw));
 67     answ[start]=0;
 68     while(q.size()){
 69         p now=q.top();
 70         if(now.self==ed)
 71             break;
 72         q.pop();
 73         if(vis[now.self])
 74             continue;
 75         vis[now.self]=true;
 76         for(int i=beg[now.self];i!=-1;i=nex[i]){
 77             int nx=to[i];
 78             if(answ[nx]>now.val+weight[i]){
 79                 answ[nx]=now.val+weight[i];
 80                 q.push({now.val+weight[i],nx,now.step+1});
 81                 stepw[nx]=now.step+1;
 82                 tarw[nx]=now.self;
 83             }
 84             if(answ[nx]==now.val+weight[i]){
 85                 if(stepw[nx]>now.step+1){
 86                     q.push({now.val+weight[i],nx,now.step+1});
 87                     stepw[nx]=now.step+1;
 88                     tarw[nx]=now.self;
 89                 }
 90             }
 91         }
 92     }
 93     answwsize=0;
 94     for(int i=ed;i!=st;i=tarw[i]){
 95         answw[++answwsize]=i;
 96     }
 97     answw[++answwsize]=st;
 98 }
 99 
100 void Dijkstrat(int start){
101     while(q.size())
102         q.pop();
103     q.push({0,start,0});
104     memset(vis,0,sizeof(vis));
105     memset(anst,0x3f3f3f3f,sizeof(anst));
106     memset(answ,0x3f3f3f3f,sizeof(answ));
107     memset(stepw,0x3f3f3f3f,sizeof(stepw));
108     memset(tart,-1,sizeof(tart));
109     answ[start]=0;
110     while(q.size()){
111         p now=q.top();
112         if(now.self==ed)
113             break;
114         q.pop();
115         if(vis[now.self])
116             continue;
117         vis[now.self]=true;
118         for(int i=beg[now.self];i!=-1;i=nex[i]){
119             int nx=to[i];
120             if(anst[nx]>now.val+tisme[i]){
121                 anst[nx]=now.val+tisme[i];
122                 answ[nx]=now.val+weight[i];
123                 q.push({now.val+tisme[i],nx,now.step+1});
124                 stepw[nx]=now.step+1;
125                 tart[nx]=now.self;
126             }
127             if(anst[nx]==now.val+tisme[i]){
128                 if(answ[nx]>now.val+weight[i]){
129                     q.push({now.val+tisme[i],nx,now.step+1});
130                     tart[nx]=now.self;
131                     stepw[nx]=now.step+1;
132                 }else if(answ[nx]==now.val+weight[i]){
133                     if(stepw[nx]>now.step+1){
134                         q.push({now.val+tisme[i],nx,now.step+1});
135                         stepw[nx]=now.step+1;
136                         tart[nx]=now.self;
137                     }
138                 }
139             }
140         }
141     }
142     ansttsize=0;
143     for(int i=ed;i!=st;i=tart[i]){
144         anstt[++ansttsize]=i;
145     }
146     anstt[++ansttsize]=st;
147 }
148 int main(){
149     ios::sync_with_stdio(false);
150     ios_base::sync_with_stdio(false);
151     cin.tie(0);
152     cout.tie(0);
153     init();
154     cin>>n>>m;
155     for(int i=1;i<=m;i++){
156         int a,b,c,d,e;
157         cin>>a>>b>>c>>d>>e;
158         if(c==1){
159             add(a,b,d,e);
160         }else{
161             add(a,b,d,e);
162             add(b,a,d,e);
163         }
164     }
165     cin>>st>>ed;
166     Dijkstraw(st);
167     int answww=answ[ed];
168     Dijkstrat(st);
169     cout<<"Time = "<<anst[ed];
170     bool flagttt=true;
171     if(answwsize==ansttsize){
172         for(int i=1;i<=answwsize;i++){
173             if(answw[i]!=anstt[i]){
174                 flagttt=false;
175                 break;
176             }
177         }
178     }else{
179         flagttt=false;
180     }
181     if(flagttt==true){
182         cout<<"; Distance = "<<answww;
183         cout<<": ";
184     //    reverse(answw.begin(),answw.end());
185         for(int i=answwsize;i!=0;i--){
186             if(i!=answwsize)
187                 cout<<" => ";
188             cout<<answw[i];
189         }
190         cout<<endl;
191     }else{
192         cout<<": ";
193         for(int i=ansttsize;i!=0;i--){
194             if(i!=ansttsize)
195                 cout<<" => ";
196             cout<<anstt[i];
197         }
198         cout<<endl;
199         cout<<"Distance = "<<answww;
200         cout<<": ";
201         for(int i=answwsize;i!=0;i--){
202             if(i!=answwsize)
203                 cout<<" => ";
204             cout<<answw[i];
205         }
206         cout<<endl;
207     }
208 }

View Code

不知道为啥我的这个代码错了一组样例（23分）

  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<iostream>
  4 #include<algorithm>
  5 #include<queue>
  6 #include<vector>
  7 using namespace std;
  8 const int maxn=505;
  9 #define INF 0x3f3f3f3f
 10 struct shudui1
 11 {
 12     int start,value;
 13     bool operator < (const shudui1 q)const
 14     {
 15         return value>q.value;
 16     }
 17 } str1;
 18 struct shudui2
 19 {
 20     int start,value1,value2;
 21 } str2;
 22 int dis[maxn],path[maxn],dp[maxn],path1[maxn],vis[maxn],path2[maxn],len1,len2;
 23 priority_queue<shudui1>r; //里面的数据默认是从小到大排序，这样就不用通过佛如循环遍历在每一次找v里面的最小值
 24 vector <shudui2>w[maxn];  //将每一个起点的值作为数组的标识
 25 //例如，1 2 3这一组数据，就是说1连接着2，那就把所有1能到的地方存到这个里面
 26 void JK1(int s,int en)
 27 {
 28     memset(dp,INF,sizeof(dp));
 29     memset(dis,INF,sizeof(dis));
 30     memset(vis,0,sizeof(vis));
 31     memset(path,-1,sizeof(path));
 32     dp[s]=0;
 33     dis[s]=0;
 34     str1.start=s;
 35     str1.value=0;
 36     r.push(str1);
 37     while(!r.empty())
 38     {
 39         int x,y;
 40         str1=r.top();
 41         r.pop();
 42         x=str1.start;
 43         y=str1.value;
 44         if(vis[x]) continue;
 45         vis[x]=1;
 46         int len=w[x].size();
 47         for(int i=0; i<len; ++i)
 48         {
 49             str2=w[x][i];
 50             if(dis[x]+str2.value1<dis[str2.start])
 51             {
 52 
 53                 dp[str2.start]=dp[x]+str2.value2;
 54                 dis[str2.start]=dis[x]+str2.value1;
 55                 path[str2.start]=x;
 56                 //printf("%d %d***
",str2.start,x);
 57                 if(!vis[str2.start])
 58                 {
 59                     str1.start=str2.start;
 60                     str1.value=dis[str2.start];
 61                     r.push(str1);
 62                 }
 63 
 64             }
 65             else if(dis[x]+str2.value1==dis[str2.start])
 66             {
 67                 if(dp[str2.start]>dp[x]+str2.value2)
 68                 {
 69                     //printf("%d %d***
",str2.start,x);
 70                     path[str2.start]=x;
 71                     dp[str2.start]=dp[x]+str2.value2;
 72                     if(!vis[str2.start])
 73                     {
 74                         str1.start=str2.start;
 75                         str1.value=dis[str2.start];
 76                         r.push(str1);
 77                     }
 78                 }
 79             }
 80         }
 81     }
 82 }
 83 void JK2(int s,int en)
 84 {
 85     memset(dp,INF,sizeof(dp));
 86     memset(dis,INF,sizeof(dis));
 87     memset(vis,0,sizeof(vis));
 88     memset(path,-1,sizeof(path));
 89     dp[s]=0;
 90     dis[s]=0;
 91     str1.start=s;
 92     str1.value=0;
 93     r.push(str1);
 94     while(!r.empty())
 95     {
 96         int x,y;
 97         str1=r.top();
 98         r.pop();
 99         x=str1.start;
100         y=str1.value;
101         if(vis[x]) continue;
102         vis[x]=1;
103         int len=w[x].size();
104         for(int i=0; i<len; ++i)
105         {
106             str2=w[x][i];
107             if(dis[x]+str2.value2<dis[str2.start])
108             {
109 
110                 dp[str2.start]=dp[x]+str2.value1;
111                 dis[str2.start]=dis[x]+str2.value2;
112                 path[str2.start]=x;
113                 //printf("%d %d***
",str2.start,x);
114 //                if(!vis[str2.start])
115 //                {
116                 str1.start=str2.start;
117                 str1.value=dis[str2.start];
118                 r.push(str1);
119                 // }
120 
121             }
122             else if(dis[x]+str2.value2==dis[str2.start])
123             {
124                 if(dp[str2.start]>dp[x]+str2.value1)
125                 {
126                     //printf("%d %d***
",str2.start,x);
127                     path[str2.start]=x;
128                     dp[str2.start]=dp[x]+str2.value1;
129 //                    if(!vis[str2.start])
130 //                    {
131                     str1.start=str2.start;
132                     str1.value=dis[str2.start];
133                     r.push(str1);
134                     //  }
135                 }
136             }
137         }
138     }
139 }
140 int main()
141 {
142     int n,m;
143     scanf("%d%d",&n,&m);
144     while(m--)
145     {
146         int x,y,z1,z2,type;
147         scanf("%d%d%d%d%d",&x,&y,&type,&z1,&z2);
148         x++;
149         y++;
150         if(type)
151         {
152             //p[x][y]=z2;
153             str2.start=y;
154             str2.value1=z1;
155             str2.value2=z2;
156             w[x].push_back(str2);
157         }
158         else
159         {
160             //p[x][y]=p[y][x]=z2;
161             str2.start=y;
162             str2.value1=z1;
163             str2.value2=z2;
164             w[x].push_back(str2);
165             str2.start=x;
166             w[y].push_back(str2);
167         }
168     }
169     int st,en,short_dis,short_time;
170     scanf("%d%d",&st,&en);
171     st++;en++;
172     JK1(st,en);
173     short_dis=dis[en];
174     int temp=en;
175     while(temp!=-1)
176     {
177         path1[len1++]=temp;
178         temp=path[temp];
179     }
180 
181     JK2(st,en);
182     short_time=dis[en];
183     temp=en;
184     while(temp!=-1)
185     {
186         path2[len2++]=temp;
187         temp=path[temp];
188     }
189     int flag=0;
190     if(len1==len2)
191     {
192         for(int i=0; i<len1; ++i)
193         {
194             if(path1[i]!=path2[i])
195             {
196                 flag=1;
197                 break;
198             }
199         }
200     }
201     else flag=1;
202 
203     if(flag)
204     {
205         printf("Time = %d: %d",short_time,st-1);
206         for(int i=len2-2; i>=0; --i)
207         {
208             printf(" => %d",path2[i]-1);
209         }
210         printf("
");
211 
212         printf("Distance = %d: %d",short_dis,st-1);
213         for(int i=len1-2; i>=0; --i)
214         {
215             printf(" => %d",path1[i]-1);
216         }
217         printf("
");
218     }
219     else
220     {
221         printf("Time = %d; Distance = %d: %d",short_time,short_dis,st-1);
222         for(int i=len1-2; i>=0; --i)
223         {
224             printf(" => %d",path1[i]-1);
225         }
226         printf("
");
227     }
228     return 0;
229 }

View Code