CodeVS/1077

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	需要注意
多源最短路	★☆☆☆☆	答案正确	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]); } }