HDU - 1874 원활 한 프로젝트 계속 (Dijkstra 와 SPFA)

원활 한 공사 가 계속되다.
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 42616 Accepted Submission(s): 15785
Problem Description 모 성 은 여러 해 동안 의 원활 한 공사 계획 을 실행 한 후에 마침내 많은 길 을 건설 하 였 다.길 을 많이 건 너 지 않 아 도 좋 지 않다. 한 도시 에서 다른 도시 로 갈 때마다 여러 가지 도로 방안 을 선택 할 수 있 고 어떤 방안 은 다른 방안 보다 걷 는 거리 가 훨씬 짧다.이것 은 행인 들 을 매우 곤란 하 게 한다.
지금 은 출발점 과 종점 을 알 고 있 습 니 다. 출발점 에서 종점 까지 가장 짧 은 거 리 를 걸 어야 하 는 지 계산 해 보 세 요.
Input 이 문 제 는 여러 그룹의 데 이 터 를 포함 하고 있 습 니 다. 파일 이 끝 날 때 까지 처리 하 십시오.각 조 의 데이터 첫 줄 은 두 개의 정수 N 과 M (0 < N < 200, 0 < M < 1000) 을 포함 하고 각각 기 존의 도시 의 수량 과 이미 건 설 된 도로 의 수량 을 대표 한다.도 시 는 각각 0 ～ N - 1 번호 로 되 어 있다.다음은 M 행 도로 정보.한 줄 에 세 개의 정수 A, B, X (0 < = A, B < N, A! = B, 0 < X < 10000) 가 있 는데 도시 A 와 도시 B 사이 에 X 의 양 방향 도로 가 있다 는 것 을 나타 낸다.다음 줄 에 두 개의 정수 S, T (0 < = S, T < N) 가 있 는데 각각 출발점 과 종점 을 대표 한다.
Output 은 각 그룹의 데이터 에 대해 한 줄 에서 가장 짧 은 걸 어야 할 거 리 를 출력 하 십시오.S 에서 T 까지 의 노선 이 존재 하지 않 으 면 출력 - 1.
Sample Input 3 3 0 1 1 0 2 3 1 2 1 0 2 3 1 0 1 1 1 2
Sample Output 2 -1
우선 대기 열 로 최적화 하면 불필요 한 조작 을 줄 일 수 있 습 니 다.경 로 를 완벽 하 게 인쇄 하려 면 경 로 를 기록 하 는 배열 을 구조 체 로 바 꾸 고 저장 거리 와 이 점 의 전구 점 은 pre 입 니 다.그리고 계산 을 마 친 후 종점 에서 앞으로 pre 교체 로 찾 은 후 거꾸로 인쇄 하면 됩 니 다.이 방법 은 이산 수학의 Dijkstra 표기 법 문제 에 도 적합 하 다.Dijkstra 코드:

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
const int N=1010;
int d[N];
vector<pair<int,int> >edge[N];
void init()
{
    for (int i=0; i<N; i++)
    {
        edge[i].clear();
        d[i]=INF;
    }
}

int main(void)
{
    int n,m,i,j,x,y,z;
    while (~scanf("%d%d",&n,&m))
    {
        init();
        for (i=1; i<=m; i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            edge[x].push_back(make_pair(y,z));
            edge[y].push_back(make_pair(x,z));
        }
        priority_queue<pair<int,int> > Q;
        int s,t;
        scanf("%d%d",&s,&t);
        Q.push(make_pair(-d[s],s));
        d[s]=0;
        while (!Q.empty())
        {
            int now=Q.top().second;
            Q.pop();
            for (i=0; i<edge[now].size(); i++)
            {
                int t=edge[now][i].first;
                if(d[t]>d[now]+edge[now][i].second)
                //           ，       ，  A->B->C  A->C  ， A C      A->C
                {
                    d[t]=d[now]+edge[now][i].second;
                    Q.push(make_pair(-d[t],t));
                }
            }
        }
        if(d[t]==INF)
            puts("-1");
        else
            printf("%d
",d[t]);
    }
    return 0;
}

SPFA 코드 (인쇄 경로):

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<string>
#include<deque>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define INF 0x3f3f3f3f 
typedef long long LL;
struct info
{
    int d;
    int pre;
};
const int N=1010;
int n,m,s,t;
info d[N];
int inq[N];
vector<pair<int,int> >vec[N];
void init()
{
    for (int i=0; i<N; i++)
    {
        d[i].d=INF;
        d[i].pre=-1;
        vec[i].clear();
        inq[i]=0;
    }
}
int main(void)
{
    int i,j,k,ans,x,y,dx;
    while (cin>>n>>m)
    {
        init();
        for (i=0; i<m; i++)
        {
            cin>>x>>y>>dx;
            vec[x].push_back(make_pair(y,dx));
            vec[y].push_back(make_pair(x,dx));
        }
        cin>>s>>t;
        queue<int> q;

        q.push(s);
        d[s].d=0;
        inq[s]=1;

        while (!q.empty())
        {
            int now=q.front();
            q.pop();
            inq[now]=0;                         
            for (i=0; i<vec[now].size(); i++)   
            {
                int v=vec[now][i].first;        
                if(d[v].d>d[now].d+vec[now][i].second)/
                {
                    d[v].pre=now;           
                    d[v].d=d[now].d+vec[now][i].second;
                    if(inq[v]==1)               
                        continue;
                    q.push(v);                  
                }    
            }
        }
        if(d[t].d==INF)
            cout<<"There is no such way"<<endl;
        else
        {
            stack<int> his;
            his.push(t);
            for (i=t; d[i].pre!=-1; i=d[i].pre)
            {       
                his.push(d[i].pre);
            }
            while (1)
            {
                cout<<his.top();
                his.pop();
                if(his.empty())
                    break;
                else
                    cout<<"-->>";
            }
            cout<<"
"<<"Total distance:"<<d[t].d<<'
'<<endl;
        }    
    }
    return 0;
}