Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## dijkstra 附代码，希望对wa的兄弟们有帮助

Posted by smallsunny at 2011-10-22 09:48:45 on Problem 2457
```#include <iostream>
#include <stdio.h>
using namespace std;
const int MAXN = 1000;
const int inf = 0x3fffffff;
int rel[MAXN+10][MAXN+10];
int dist[MAXN+10];
int pre[MAXN+10];
bool visit[MAXN+10];
int ans[MAXN+10];
int cnt;
int m, n;
void dijkstra()
{
for(int i = 1; i <= n; i++)
{
visit[i] = false;
dist[i] = inf;
}
dist[1] = 0;
for(int i = 1; i <= n; i++)
{
int mmin = inf;
int pos;
for(int j = 1; j <= n; j++)
{
if(!visit[j] && dist[j]<mmin)
{
mmin = dist[j];
pos = j;
}
}
visit[pos] = true;
for(int j = 1; j <= n; j++)
{
if(!visit[j] && dist[j] > dist[pos]+rel[pos][j])
{
pre[j] = pos;
dist[j] = dist[pos]+rel[pos][j];
}
}
}
}
int main()
{
//freopen("in.txt", "r", stdin);
while(scanf("%d%d", &m, &n) != EOF)
{
cnt = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++) rel[i][j] = inf;
}
for(int i = 1; i <= m; i++)
{
int u, v;
scanf("%d%d", &u, &v);
rel[u][v] = 1;
}
dijkstra();
if(dist[n] == inf) printf("-1\n");
else
{
ans[cnt++] = n;
int tmp = pre[n];
while(tmp != 1)
{
ans[cnt++] = tmp;
tmp = pre[tmp];
}
ans[cnt++] = 1;
printf("%d\n", cnt);
for(int i = cnt-1; i >= 0; i--) printf("%d\n", ans[i]);
}
}
return 0;
}
```

Followed by: