sdut 3562 Proxy (迪杰斯特拉+反向建树）---------------------C语言——菜鸟级
sdut 3562 Proxy (迪杰斯特拉+反向建树）---------------------C语言——菜鸟级
http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/3562.html 1640: 题目 B Proxy 时间限制: 1 Sec 内存限制: 128 MB 提交: 5 解决: 2 [提交][状态][讨论版] [Edit] [TestData] 题目描述
由于GFW (Great Firewall)，我们不能直接访问很多网站，如Facebook、Twitter、YouTube等，
但在代理服务器和代理服务器的帮助下，我们可以很容易地访问这些网站。
您有多个代理服务器的列表，其中一些可以直接连接，而另一些则不能。
但是您可以通过其他代理服务器通过单向连接访问代理服务器。我们都知道，网络访问的滞后将决定我们对访问的感受。
你有一个非常智能的代理软件，一旦你选择了一个可直接访问的代理服务器，你就会发现你可以找到最慢的方法到达网站。
你知道每一个联系的滞后。你访问的滞后是你整个联系的全部滞后。您希望最小化访问延迟，您将选择哪个代理服务器?
输入
输入多个测试用例，
第一行是整数T (T <= 100)，表示测试用例的数量。
每个测试用例的第一行是两个整数N (0 <= N <= 1000)， M (0 <= M <= 20000)。
N是代理服务器的数量(从1到N)。0是你的电脑的标签，(N+1)是目标网站服务器的标签。
然后M行，每一行包含三个u, v, w (0 <= u, v <= N + 1, 1 <= w <= 1000)，表示u可以直接连接到v，滞后是w。
输出
对于每个测试用例，您将选择直接连接的代理服务器的一个整数。您只能选择直接从您的计算机连接的代理服务器。
如果有多个选择，您应该用最少的标签输出代理服务器。如果你不能以任何方式访问目标网站，输出“-1”(没有引号)。
如果你可以直接访问目标网站，而且延迟是最小的，输出“0”(没有引号)。
样例输入 4 3 6 0 1 10 1 2 1 2 4 4 0 3 2 3 2 1 3 4 7 2 4 0 2 10 0 1 5 1 2 4 2 1 7 1 3 0 2 1 0 1 2 1 2 1 1 3 0 2 10 0 1 2 1 2 1
样例输出 3 -1 0 1
思路：迪杰斯特拉 反向建树
#include<stdio.h>
#include<string.h>
#define N 1002
#define Min(a,b) a>b?b:a
#define INF 1000000
int dis[N],bj[N];
int mp[N][N];int n;
void djsk(int v)
{
int i,j,k,min;
for(i=0;i<=n;i++)
dis[i]=mp[v][i];//初始化dis数组 dis[i]=5代表从起始点到i点的最短距离
dis[v]=0;// v 代表起始节点 自己到自己为0
bj[v]=1;// 标记 已找到短路
for(i=0;i<=n;i++)// i 代表已经找到的最短路条数
{
min=INF;k=0;
for(j=0;j<=n;j++)//从未找到最短路径元素中找一个路径最短的
if(!bj[j]&&dis[j]<min)min=dis[j],k=j;
bj[k]=1;// 标记 已找到短路
for(j=0;j<=n+1;j++)//用但前最短路节点更新未找到最短路的节点
if(!bj[j]&&dis[j]>(dis[k]+mp[k][j]))dis[j]=dis[k]+mp[k][j];
}
}
int main()
{
int T,m,i,j,u,v,w,ans;
scanf("%d",&T);
while(T--)
{ memset(bj,0,sizeof(bj));
scanf("%d%d",&n,&m);
for(i=0;i<=n+1;i++)
for(j=0;j<=n+1;j++)
mp[i][j]=INF;
for(i=0;i<=n+1;i++)mp[i][i]=0;
for(i=1;i<=m;i++)
{scanf("%d%d%d",&u,&v,&w);
mp[v][u]=w;
}
djsk(n+1);
if(dis[0]==INF)printf("-1\n");
else
{ ans=INF;
for(i=1;i<=n+1;i++)
if(dis[i]+mp[i][0]==dis[0]&&i<ans)ans=i;
if(ans==n+1)printf("0\n");
else printf("%d\n",ans);
}
}
return 0;
}#include<stdio.h>
#include<string.h>
#define N 1002
#define Min(a,b) a>b?b:a
#define INF 1000000
int dis[N],s[2][N];
int mp[N][N];int n;
void djsk(int v)
{
int i,j,k,min,q=0,d=0,c=0;
for(i=0;i<=n;i++)
s[c][q++]=i,dis[i]=mp[v][i];//初始化dis数组 dis[i]=5代表从起始点到i点的最短距离
dis[v]=0;// v 代表起始节点 自己到自己为0
while(q)//没有未找到最短路的元素
{
min=INF;k=-1;
for(j=0;j<q;j++)//从未找到最短路径元素中找一个路径最短的
if(dis[s[c%2][j]]<min)
{ min=dis[s[c%2][j]];
if(k!=-1)s[(c+1)%2][d++]=k;
k=s[c%2][j];
}
else s[(c+1)%2][d++]=s[c%2][j];
if(q==d)break;//寻找无改变 则未联通
for(j=0;j<d;j++)//用但前最短路节点更新未找到最短路的节点
if(dis[s[(c+1)%2][j]]>(dis[k]+mp[k][s[(c+1)%2][j]]))dis[s[(c+1)%2][j]]=dis[k]+mp[k][s[(c+1)%2][j]];
c=(c+1)%2;q=d;d=0;//交换层次
}
}
int main()
{
int T,m,i,j,u,v,w,ans;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(i=0;i<=n+1;i++)
for(j=0;j<=n+1;j++)
mp[i][j]=INF;
for(i=0;i<=n+1;i++)mp[i][i]=0;
for(i=1;i<=m;i++)
{scanf("%d%d%d",&u,&v,&w);
mp[v][u]=w;
}
djsk(n+1);
if(dis[0]==INF)printf("-1\n");
else
{ ans=INF;
for(i=1;i<=n+1;i++)
if(dis[i]+mp[i][0]==dis[0]&&i<ans)ans=i;
if(ans==n+1)printf("0\n");
else printf("%d\n",ans);
}
}
return 0;
}腾讯云开发者
