dijkstra 최 단 경로 알고리즘 템 플 릿

제목 은 무방 향도 로 기점 s 와 종점 t 를 제시한다.

//               
//   uva 10986
//      dijkstra  ，        
#include 

using namespace std;
const int MAX_V=20000+1;
struct edge
{
    int to,cost;
};
typedef pair<int,int> P;
int V;
vector G[MAX_V];
int d[MAX_V];
bool used[MAX_V];
int dijkstra(int s,int t)
{
    priority_queue
vector
,greater
 > que;
    memset(used,false,sizeof(used));
    fill(d ,d+V,INT_MAX);
    d[s]=0;
    que.push(P(0,s));
    while(!que.empty())
    {
        P p=que.top();
        que.pop();
        int v=p.second;
        if(d[v]
continue;
        used[v]=true;
        for(int i=0;iif(d[e.to]>d[v]+e.cost)
            {
                d[e.to]=d[v]+e.cost;
                que.push(P(d[e.to],e.to));
            }
        }
    }
    return d[t];
}
int n,m,S,T;
void ini()
{
    for(int i=0;i<=V;i++)
        G[i].clear();
}
int main()
{
    ios::sync_with_stdio(false);
    int Case,k=0;
    cin>>Case;
    while(Case--)
    {
        cin>>n>>m>>S>>T;
        V=n;
        ini();
        for(int i=0;iint a,b,c;
            cin>>a>>b>>c;
            G[a].push_back(edge{b,c});
            G[b].push_back(edge{a,c});
        }
        int ans=dijkstra(S,T);
        cout<<"Case #"<": ";
        if(ans==INT_MAX)
            cout<<"unreachable"<else
            cout<return 0;
}