poj 3463 最短路与次短路&&统计个数
题意:求最短路和比最短路长度多1的次短路的个数
本来想图(有)方(模)便(版)用spfa的,结果妹纸要我看看dijkstra怎么解....
写了三遍orz
Ver1.0:堆优化+邻接表,WA
1 //不能用堆优化+邻接表,因为需要处理dis[i][0]和dis[i][1]两套,如果都挤到一个堆里就乱套了 2 3 #include <iostream> 4 #include <cstdio> 5 #include <queue> 6 #include <cstring> 7 #include <vector> 8 using namespace std; 9 const int Ni = 10000; 10 const int INF = 1<<27; 11 struct node 12 { //eg[i].x eg[i].d i:start x:end d:distance 13 int x,d; 14 node(){} 15 node(int a,int b){x=a;d=b;} 16 bool operator < (const node & a) const //用于优先队列, 取距离原点最近的点 17 { 18 if(d==a.d) return x<a.x; 19 else return d > a.d; 20 } 21 }; 22 vector<node> eg[Ni]; 23 int dis[Ni][5],cnt[Ni][5],n,T; 24 25 void Dijkstra(int s) //1.比最短路短2.等于最短路3.长于最短路但短于次短路4.等于次短路 26 { 27 memset(dis,0,sizeof(dis)); 28 memset(cnt,0,sizeof(cnt)); 29 30 int i; 31 for(i=0;i<=n;i++) 32 { 33 dis[i][1]=INF; 34 dis[i][2]=INF; 35 } 36 dis[s][1]=0; 37 dis[s][2]=0; 38 priority_queue<node> q; //q:优先队列,用来取离原点最近的顶点 39 q.push(node(s,dis[s][1])); //初始只有一个原点自己 40 while(!q.empty()) 41 { 42 node x=q.top();q.pop(); 43 for(i=0;i<eg[x.x].size();i++) 44 { 45 node y=eg[x.x][i]; 46 if(dis[y.x][1]>x.d+y.d) //1 47 { 48 cnt[y.x][1]=1; 49 cnt[y.x][2]=1; 50 dis[y.x][2]=dis[y.x][1]; 51 dis[y.x][1]=x.d+y.d; 52 q.push(node(y.x,dis[y.x][1])); 53 } 54 else if (dis[y.x][1]==x.d+y.d) //2 55 { 56 cnt[y.x][1]++; 57 } 58 else if ((dis[y.x][1]<x.d+y.d)&&(x.d+y.d<dis[y.x][2])) //3 59 { 60 cnt[y.x][2]=1; 61 dis[y.x][2]=x.d+y.d; 62 } 63 else if (x.d+y.d==dis[y.x][2]) //4 64 { 65 cnt[y.x][2]++; 66 } 67 } 68 } 69 } 70 71 void debug() 72 { 73 cout<<"Debug only"<<endl; 74 for (int i=1;i<=n;i++) 75 printf("%d - %d %d - %d %d ",i,dis[i][1],cnt[i][1],dis[i][2],cnt[i][2]); 76 cout<<ans1<<" "<<ans2<<endl; 77 78 } 79 80 int main() 81 { 82 scanf("%d",&T); 83 while (T--) 84 { 85 int a,b,d,m,k,st; 86 scanf("%d%d",&n,&m); 87 for(int i=0;i<=n;i++) eg[i].clear(); 88 while(m--) 89 { 90 scanf("%d%d%d",&a,&b,&d); 91 eg[a].push_back(node(b,d)); 92 } 93 scanf("%d %d",&k,&st); 94 Dijkstra(k); 95 96 debug1(); 97 98 int t1=dis[st][1],t2=dis[st][2],ans1=cnt[st][1],ans2; 99 if (t2-t1==1) 100 ans2=cnt[st][2]; 101 else ans2=0; 102 printf("%d ",ans1+ans2); 103 } 104 105 return 0; 106 }
Ver2.0:邻接矩阵,WA
1 //不能用邻接矩阵,因为会有重边 2 3 #include <iostream> 4 #include <cstring> 5 using namespace std; 6 #define MAXINT 9999999 7 8 int minx,minj,x,y,t,k,n,m,tmp,st,flag; 9 int v[1010][3],d[1010][3],cnt[1010][3],a[1010][1010]; 10 11 int main() 12 { 13 int T; 14 cin>>T; 15 while (T--) 16 { 17 cin>>n>>m; 18 memset(a,0,sizeof(a)); 19 memset(d,MAXINT,sizeof(d)); 20 memset(v,0,sizeof(v)); 21 memset(cnt,0,sizeof(cnt)); 22 23 for (int i=1;i<=m;i++) 24 { 25 cin>>x>>y>>t; 26 a[x][y]=t; 27 } 28 cin>>k>>st; 29 d[k][1]=0; //d[k][2]=0; 30 cnt[k][1]=1; // cnt[k][2]=1; 31 32 for (int i=1;i<=2*n;i++) 33 { 34 minx=MAXINT; 35 for (int j=1;j<=n;j++) 36 { 37 if ((v[j][1]==0)&&(d[j][1]<minx)) 38 { 39 minx=d[j][1]; 40 minj=j; 41 flag=1; 42 } 43 if ((v[j][2]==0)&&(d[j][2]<minx)) 44 { 45 minx=d[j][2]; 46 minj=j; 47 flag=2; 48 } 49 } 50 v[minj][flag]=1; 51 for (int j=1;j<=n;j++) 52 // if ((v[j][1]==0)&&(a[minj][j]>0)) 53 if (a[minj][j]>0) 54 { 55 tmp=minx+a[minj][j]; 56 57 if (tmp<d[j][1]) 58 { 59 d[j][2]=d[j][1]; 60 d[j][1]=tmp; 61 cnt[j][2]=cnt[j][1]; 62 cnt[j][1]=cnt[minj][flag]; 63 } 64 else if (tmp==d[j][1]) 65 { 66 cnt[j][1]+=cnt[minj][flag]; 67 } 68 else if (tmp<d[j][2]) 69 { 70 d[j][2]=tmp; 71 cnt[j][2]=cnt[minj][flag]; 72 } 73 else if (tmp==d[j][2]) 74 { 75 cnt[j][2]+=cnt[minj][flag]; 76 } 77 } 78 } 79 80 for (int i=1;i<=n;i++) 81 cout<<d[i][1]<<" "<<cnt[i][1]<<" = "<<d[i][2]<<" "<<cnt[i][2]<<endl; 82 cout<<endl; 83 int t1=d[st][1],t2=d[st][2],ans1=cnt[st][1],ans2; 84 if (t2==t1+1) ans2=cnt[st][2]; else ans2=0; 85 cout<<ans1+ans2<<endl; 86 } 87 return 0; 88 }