?? 最短路 隊長:北大d題.txt
字號:
X-Ray(361096807) 08:29:24
昨天北大比賽最短路題的代碼:
#include <cstdio>
#include <vector>
#include <queue>
#include <list>
using namespace std;
const int N = 1010;
int dis[N];
int tmp[N];
int n,m;
vector< list< pair<int,int> > >ad;
int SPFA(int src,int des)
{
bool st[N] = {false};
int i,j,k;
queue<int>q;
for(i=1;i<=n;i++) dis[i] = 10000000;
dis[src] = 0;
q.push(src); st[src] = true;
while(!q.empty())
{
i = q.front();
q.pop();
list< pair<int,int> >::iterator it;
for(it = ad[i].begin(); it != ad[i].end(); it++)
{
j = it->first;
k = it->second;
if(dis[i]+k<dis[j])
{
dis[j] = dis[i] + k;
if(!st[j]) { st[j] = true; q.push(j); }
}
}
st[i] = false;
}
return dis[des];
}
int main()
{
int i,j,k,src;
scanf("%d%d%d",&n,&m,&src);
ad.resize(n+1);
for(;m;m--)
{
scanf("%d%d%d",&i,&j,&k);
ad[i].push_back(make_pair(j,k));
}
SPFA(src,src);
for(i=1;i<=n;i++) tmp[i] = dis[i];
int ans = 0;
for(i=1;i<=n;i++)
{
int x = SPFA(i,src);
if(x+tmp[i]>ans) ans = x+tmp[i];
}
printf("%d\n",ans);
return 0;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -