poj 1797 最短路变形

传送门

题意：给你n个点，m条路，每条路有重量限制，问1到n最多能运多重的货物。

思路：一开始想dfs+剪枝，结果超时啦！我还是太年轻。

后来就根据求最短路的方法稍加变形，就过了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define maxn 1<<29
using namespace std;
int t,n,m,en;
int fst[1005],next[1000005],node[1000005],w[1000005];
int d[1005];
bool inq[1005];
void add(int u,int v,int c)
{
next[++en]=fst[u];
fst[u]=en;
node[en]=v;
w[en]=c;
}
void init()
{
int u,v,c;
en=0;
memset(fst,-1,sizeof(fst));
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&c);
add(u,v,c);
add(v,u,c);
}
}
void spfa()
{
queue<int>q;
memset(inq,0,sizeof(inq));
memset(d,0,sizeof(d));
d[1]=maxn;
q.push(1);
inq[1]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
inq[u]=0;
for(int i=fst[u];i!=-1;i=next[i])
{
int v=node[i];
int mi=min(w[i],d[u]);
if(d[v]<mi)
{
d[v]=mi;
if(!inq[v])
{
q.push(v);
inq[v]=1;
}
}
}
}
}
int main()
{
int ca=1;
scanf("%d",&t);
while(t--)
{
init();
spfa();
printf("Scenario #%d:n%dnn",ca++,d[n]);
}
return 0;
}

最后

以上就是发嗲期待为你收集整理的poj 1797 最短路变形的全部内容，希望文章能够帮你解决poj 1797 最短路变形所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。