| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 需要注意 |
|---|---|---|---|---|---|
| 多源最短路 | ★☆☆☆☆ | 答案正确 | 100 | 2015-7-20 19:47:39 | 无 |
| 1077.cpp代码已折叠
展开折叠内容
|
|---|
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<set>
#include<queue>
#include<cstring>
#include<climits>
#include<cmath>
using namespace std;
#define lld long long
queue<int> p;
vector< pair<int,int> > L[256]={};
int Dis[256][256]={};
#define foreach(i,a) for(typeof(a.begin()) i=a.begin();i!=a.end();++i)
int main(){
int n;
scanf("%d",&n);
memset(Dis,15,sizeof(Dis));//设置初值为很大的值//
int Ans=INT_MAX;int Ansc;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
//新建路径//
int d;
scanf("%d",&d);
L[i].push_back( make_pair(j,d) );
}
}
//伦家就是喜欢SPFA口亨，100个点肯定也不会出问题//
for(int r=1;r<=n;++r)
{
p.push(r);Dis[r][r]=0;
while(!p.empty())//队列非空//
{
foreach(i,L[p.front()])//遍历//
{
if(Dis[r][p.front()]+i->second<Dis[r][i->first])//判断Dis是否更优//
{
Dis[r][i->first]=Dis[r][p.front()]+i->second;//更新目标点并入队//
p.push(i->first);
if(isupper(i->first))//统计Ans//
{
if(Dis[r][i->first]<Ans)
{
Ans=Dis[r][i->first];
Ansc=i->first;
}
}
}
}
p.pop();
}
}
//由于查询可能很多，先计算后处理查询//
int Q;
scanf("%d",&Q);
for(int i=1;i<=Q;++i)
{
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",Dis[x][y]);
}
}
|
CloudLunar