这题很早之前就遇到过，是pat留给我的第一印象，然而昨天却有点写不出来。今天dfs用了10分钟不到写出来了。dij用了大约15分钟，捉虫花了一点时间。
dfs：
注意剪枝的时候别剪错就行了。
#include <stdio.h> #include <memory.h> #include <math.h> #include <string> #include <vector> #include <set> #include <stack> #include <queue> #include <algorithm> #include <map> #define I scanf #define OL puts #define O printf #define F(a,b,c) for(a=b;a<c;a++) #define FF(a,b) for(a=0;a<b;a++) #define FG(a,b) for(a=b-1;a>=0;a--) #define LEN 1010 #define MAX (1<<30)+1 #define V vector<int> using namespace std; int n,m,s,e; int team_set[LEN]; int g[LEN][LEN]; int way_cnt=1; int best_cost=MAX; int best_team=0; int vis[LEN]; void dfs(int v,int cost,int team){ if(v==e){ if(cost<best_cost){ best_cost=cost; best_team=team; way_cnt=1; }else if(cost==best_cost){ way_cnt++; if(team>best_team) best_team=team; } return; } vis[v]=1; int i; //↓注意剪枝的判断语句，不要把≤写成＜ FF(i,n) if(g[v][i] && !vis[i] && cost+g[v][i]<=best_cost){ dfs(i,cost+g[v][i],team+team_set[i]); } vis[v]=0; } int main(){ // freopen("D:\CbWorkspace\PAT\最短路径\1003.txt","r",stdin); int a,b,c,i; I("%d%d%d%d",&n,&m,&s,&e); FF(i,n) I("%d",&team_set[i]); FF(i,m){ I("%d%d%d",&a,&b,&c); g[a][b]=c; g[b][a]=c; } dfs(s,0,team_set[s]); printf("%d %d ",way_cnt,best_team); return 0; }
dij：
#include <stdio.h> #include <memory.h> #include <math.h> #include <string> #include <vector> #include <set> #include <stack> #include <queue> #include <algorithm> #include <map> #define I scanf #define OL puts #define O printf #define F(a,b,c) for(a=b;a<c;a++) #define FF(a,b) for(a=0;a<b;a++) #define FG(a,b) for(a=b-1;a>=0;a--) #define LEN 1010 #define MAX (1<<30)-1 #define V vector<int> using namespace std; int n,m,s,e; int team_set[LEN]; int g[LEN][LEN]; int way_cnt[LEN]; int vis[LEN]; int dist[LEN]; int team[LEN]; int main(){ // freopen("D:\CbWorkspace\PAT\最短路径\1003.txt","r",stdin); int a,b,c,i; I("%d%d%d%d",&n,&m,&s,&e); FF(i,n) I("%d",&team_set[i]); fill(g[0],g[0]+LEN*LEN,MAX); fill(dist,dist+LEN,MAX); FF(i,m){ I("%d%d%d",&a,&b,&c); g[a][b]=c; g[b][a]=c; } dist[s]=0; team[s]=team_set[s]; way_cnt[s]=1; while(1){ int u=-1,d=MAX; FF(i,n){ if(!vis[i] && dist[i]<d){ u=i; d=dist[i]; } } if(u<0) break; vis[u]=1; FF(i,n) if(!vis[i]){ if(dist[u]+g[u][i]<dist[i]){ dist[i]=dist[u]+g[u][i]; team[i]=team[u]+team_set[i]; way_cnt[i]=way_cnt[u]; }else if(dist[u]+g[u][i]==dist[i]){ way_cnt[i]+=way_cnt[u]; if(team[i]<team[u]+team_set[i]){ team[i]=team[u]+team_set[i]; } } } } printf("%d %d ",way_cnt[e],team[e]); return 0; }
bug出现在多条最短路径的更新问题上。没有写else if 而是写了 if ，导致出错。