题意: 给你一个图, 图中每个点有对应的危险值, q 个询问, 每个询问给出起点, 终点, 限制值, 需要你计算出从起点走到终点不走那些危险值超过限制值的最短路;(起点和终点的危险值不算)
解题思路: 一开始看题目给了 10s, 想的是用 d 每次询问跑一遍 dij, 在 dij 里面 + 一个限制, 但超时了 (讲道理, 感觉 10s 够啊)... 然后看别人的解法使用三维 floyd 解决的, dp[k][i][j],k 表示用完危险值排名为 k 的点松弛后的当前最短路的值
代码:
- #include<bits/stdc++.h>
- using namespace std;
- struct node
- {
- int id;
- int val;
- }a[250];
- const int inf=0x3f3f3f3f;
- int dp[250][250][250];
- int n,m,t,cnt;
- int x,y,w;
- bool cmp(node a,node b)
- {
- return a.val<b.val;
- }
- int main()
- {
- scanf("%d",&t);
- while(t--)
- {
- memset(dp,inf,sizeof(dp));
- scanf("%d%d",&n,&m);cnt++;
- for(int i=1;i<=n;i++)
- a[i].id=i;
- for(int i=1;i<=n;i++)
- scanf("%d",&a[i].val);
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- scanf("%d",&dp[0][i][j]);
- sort(a+1,a+1+n,cmp);// 按危险值排序
- for(int k=1;k<=n;k++)
- {
- for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=n;j++)
- {
- dp[k][i][j]=min(dp[k-1][i][j],dp[k-1][i][a[k].id]+dp[k-1][a[k].id][j]);
- }
- }
- }//floyd
- printf("Case #%d:\n",cnt);
- while(m--)
- {
- scanf("%d%d%d",&x,&y,&w);
- int pos=0;
- for(int i=1;i<=n;i++)
- {
- if(a[i].val<=w)
- pos=i;// 找到对应在哪个危险值的点结束
- }
- printf("%d\n",dp[pos][x][y]);
- }
- }
- }
来源: http://www.bubuko.com/infodetail-3118594.html