HDU 2066-한 사람의 여행(그림)

HDU 2066-혼자 만 의 여행
제목
[http://acm.hdu.edu.cn/showproblem.php?pid=2066]
제목
일부 출발점,일부 종점,그리고 일부 변 의 권 리 를 정 하여 무 방향 도 를 구성 하고 모든 최 단 경로 와 중의 최소 치 를 물 습 니 다.
해제
0 을 유일한 출발점 으로 하고 다른 출발점 에서 0 까지 의 권 리 는 0 이 며 Dijkstra 알고리즘 을 한 번 사용 하면 출발점 에서 각 점 까지 의 최소 경로 와 마지막 으로 모든 종점 의 최소 경로 와 최소 값 을 계산 하면 됩 니 다.
Dijkstra 알고리즘 에 대하 여
이것 을 참고 하여 비교적 상세 한[https://www.cnblogs.com/jason2003/p/7222182.html]출발점 을 정 하고 이 출발점 에서 다른 점 까지 의 최소 경로 와 그 가 마이너스 변 에 적용 되 지 않도록 주의해 야 한다.대략적인 원 리 는 다음 과 같다.
4.567917.'소스'가 있어 야 한다.중간 값 으로 다른 변 을 이완 시 켜 야 한다4.567917.'소스'로 할 수 있 는 점 은 반드시 출발점 에서 이 점 까지 의 최소 경로 와 4.567918 을 확정 해 야 한다.
4.567917.어떤 점 은 이미'소스'가 된 후에 모든 변 이 더 이상 느슨 해 질 수 없다(최소 경로 와 이미 계산)

(두 번 째 점 의 보충 으로)다음'원'은 바로 이 원 이 다른 모든 변 에 느슨 해진 후에 출발점 에서 가장 가 까 운 점(증명 생략)이다

실현 은 대략:
그림 은 이미 알 고 있 는 것 이 어야 한다4.567917.한 배열 로 어떤 정점 이 소스 가 되 었 는 지 표시 하고 다른 배열 은 다른 점 에서 출발점 까지 의 거 리 를 저장 합 니 다(점차적으로 업데이트 되 었 습 니 다)

한 변 수 를 사용 하여 현재'소스'의 정점 을 나타 내 고 다른 변 수 는 원점 에서 가장 가 까 운 점 을'소스'로 찾 습 니 다

4.567917.출발점 에서 특정한 점 까지 의 거리 가 출발점 에서'소스'까지 의 거리 보다 크 면 이 변 은 느슨 해 져 야 한다4.567917.모든 점 에서'소스'를 한 적 이 있 거나 다음'소스'에서 출발점 까지 의 거리 가 무한 원 일 때 계산 이 완성 된다

const int maxn = (int)1e5+7;
const int INF = (int)2e9+7;
int i,j,k;
int map[maxn][maxn];//         
bool vis[maxn];int dis[maxn];//vis        ，dis           
int ori,minn,ver,sta;//ori      ，minn        ,ver    ,sta   
void dijkstra(){
    for(i=1;i<=ver;i++){
        vis[i]=0;
        dis[i]=map[sta][i];//  sta   i      INF
    }//     
    vis[sta]=1;//    sta         
    for(i=1;i<ver;i++){//     ver  
        minn=INF;
        for(j=1;j<=ver;j++)
            if(!vis[j]&&dis[j]<minn){//                     
                ori=j;
                minn=dis[j];
            }
        vis[ori]=1;//    ，  
        if(minn==INF)//             ，  
            break;
        for(j=1;j<=ver;j++)
            if(!vis[j])//        
                dis[j]=min(dis[j],dis[ori]+map[ori][j]);
    }
}

이루어지다

#include 
#include 
using namespace std;
const int maxn = 1200;
const int INF = (int)2e9+7;
int i,j,k;
int T,S,D;
int a,b,t;
int sta,tep;

int map[maxn][maxn];
int vis[maxn],dis[maxn];
int ori,minn,ver,ans;
int main(){
    while(~scanf("%d%d%d",&T,&S,&D)){
        for(i=0;i<maxn;i++){
            for(j=0;j<maxn;j++)
                map[i][j]=INF;
            map[i][i]=0;
            vis[i]=0;
            dis[i]=INF;
        }
        ori=ver=0;
        //      
        for(i=0;i<T;i++){
            scanf("%d%d%d",&a,&b,&t);
            if(t<map[a][b])//      ，     ab         
                map[a][b]=map[b][a]=t;
            ver=max(max(ver,a),b);//      
        }
        for(i=0;i<S;i++){
            scanf("%d",&sta);
            map[0][sta]=map[sta][0]=0;//       0
        }
        //       ，   ver，   dijkstra
        for(i=0;i<=ver;i++)
            dis[i]=map[0][i];
        vis[0]=1;
        for(i=0;i<ver;i++){
            minn=INF;
            for(j=0;j<=ver;j++)
                if(!vis[j]&&dis[j]<minn){
                    ori = j;
                    minn = dis[j];
                }
            if(minn==INF)
                break;
            vis[ori] = 1;
            for(j=0;j<=ver;j++)
                if(!vis[j])
                    dis[j]=min(dis[j],dis[ori]+map[ori][j]);
        }
        ans = INF;
        for(i=0;i<D;i++){
            scanf("%d",&tep);//    
            ans=min(ans,dis[tep]);
        }
        printf("%d
",ans);
    }
}