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

AC (/≧▽≦)/

Posted by 1243295518 at 2019-02-27 13:34:50 on Problem 2457
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
#include<map>
#include<math.h>
#include<vector>
#include<queue>
#include<stack>
#define inf 99999999
using namespace std;
int n,m,e[1010][1010],d[1010],a,b,vis[1010];
stack<int> st;
void init()
{
	for(int i=1;i<=n;i++)
	{
		d[i]=i==1?0:inf;
		for(int j=1;j<=n;j++)
		e[i][j]=i==j?0:inf;
	}
}
void input()
{
	for(int i=1;i<=m;i++) 
	{
		cin>>a>>b;
		e[a][b]=1;
	}
}
void dijkstra()
{
	for(int i=1;i<=n;i++)
	{
		int mins=inf,x;
		for(int j=1;j<=n;j++) if(!vis[j]&&d[j]<mins)mins=d[x=j];
		vis[x]=1;
		for(int j=1;j<=n;j++) d[j]=min(d[j],d[x]+e[x][j]);
	}
}
void print()
{
	if(d[n]>9999999)
	{
		cout<<-1;
		return;
	}
	st.push(n);
	for(int i=n;i!=1;)
	{
		for(int j=1;j<=n;j++)
		if(e[j][i]&&d[i]==d[j]+e[j][i])st.push(i=j);
	}
	cout<<st.size()<<endl;
	while(!st.empty())
	{
		cout<<st.top()<<endl;
		st.pop();
	}
}
int main()
{
	cin>>m>>n;//边,点 
	init();
	input();
	dijkstra();
	print();
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator