网站建设需要在哪备案,织梦网站地图怎么做xml,做网站推广销售,荆州哪里做网站1 /* 2 *题目大意#xff1a; 3 *在一个有向图中,求从s到t两个点之间的最短路和比最短路长1的次短路的条数之和; 4 * 5 *算法思想#xff1a; 6 *用A*求第K短路,目测会超时,直接在dijkstra算法上求次短路; 7 *将dist数组开成二维的,即dist[v][2],第二维分别用于记录最短… 1 /* 2 *题目大意 3 *在一个有向图中,求从s到t两个点之间的最短路和比最短路长1的次短路的条数之和; 4 * 5 *算法思想 6 *用A*求第K短路,目测会超时,直接在dijkstra算法上求次短路; 7 *将dist数组开成二维的,即dist[v][2],第二维分别用于记录最短路和次短路; 8 *再用一个cnt二维数组分别记录最短路和次短路的条数; 9 *每次更新路径的条数时,不能直接加1,,应该加上cnt[u][k],k为次短路径或者最短路径的标记; 10 *图有重边,不能用邻接矩阵存储; 11 *不知道为什么,题目上说的是N and M, separated by a single space, with 2≤N≤1000 and 1 ≤ M ≤ 10000; 12 *而我的代码硬是把N开成1W了才过,求解释,RE了无数次,擦; 13 **/ 14 #includeiostream 15 #includecstdio 16 #includecstring 17 #includestring 18 #includealgorithm 19 using namespace std; 20 21 const int N11111; 22 const int M111111; 23 const int INF0xffffff; 24 25 struct node 26 { 27 int to; 28 int w; 29 int next; 30 }; 31 32 node edge[N]; 33 int head[N]; 34 35 int dist[N][2],cnt[N][2]; 36 bool vis[N][2]; 37 int n,m,s,t,edges; 38 39 void addedge(int u,int v,int w) 40 { 41 edge[edges].ww; 42 edge[edges].tov; 43 edge[edges].nexthead[u]; 44 head[u]edges; 45 } 46 47 int dijkstra() 48 { 49 int k; 50 for(int i0; in; i) 51 { 52 dist[i][0]dist[i][1]INF; 53 vis[i][0]vis[i][1]0; 54 cnt[i][0]cnt[i][1]0; 55 } 56 cnt[s][0]1,dist[s][0]0; 57 58 for(int i1; in*2; i) 59 { 60 int u-1; 61 int min_distINF; 62 for(int j1; jn; j) 63 for(int flag0; flag2; flag) 64 if(!vis[j][flag]dist[j][flag]min_dist) 65 { 66 min_distdist[j][flag]; 67 uj; 68 kflag; 69 } 70 if(u-1) 71 break; 72 vis[u][k]true; 73 for(int ehead[u]; e!-1; eedge[e].next) 74 { 75 int jedge[e].to; 76 int tmpdist[u][k]edge[e].w; 77 78 if(tmpdist[j][0])//tmp小于最短路径长: 79 { 80 dist[j][1]dist[j][0];//次短路径长 81 cnt[j][1]cnt[j][0];//次短路径计数 82 dist[j][0]tmp;//最短路径长 83 cnt[j][0]cnt[u][k];//最短路径计数 84 } 85 86 else if(tmpdist[j][0])//tmp等于最短路径长 87 { 88 cnt[j][0]cnt[u][k];//最短路径计数 89 } 90 91 else if(tmpdist[j][1])//tmp大于最短路径长且小于次短路径长 92 { 93 dist[j][1]tmp;//次短路径长 94 cnt[j][1]cnt[u][k];//次短路径计数 95 } 96 97 else if(tmpdist[j][1])//tmp等于次短路径长 98 { 99 cnt[j][1]cnt[u][k];//次短路径计数
100 }
101 }
102 }
103
104 int rescnt[t][0];
105 if(dist[t][0]1dist[t][1])//判断最短路和次短路是否相差1
106 rescnt[t][1];
107 return res;
108 }
109
110 int main()
111 {
112 //freopen(C:\\Users\\Administrator\\Desktop\\kd.txt,r,stdin);
113 int tcase;
114 scanf(%d,tcase);
115 while(tcase--)
116 {
117 edges0;
118 scanf(%d%d,n,m);
119 memset(head,-1,sizeof(head));
120 int u,v,w;
121 for(int i0; im; i)
122 {
123 scanf(%d%d%d,u,v,w);
124 addedge(u,v,w);
125 }
126 scanf(%d%d,s,t);
127 printf(%d\n,dijkstra());
128 }
129 return 0;
130 } 转载于:https://www.cnblogs.com/Hammer-cwz-77/p/7337212.html
