出门旅行(tour)

题目描述:

在神奇的 oi 国度，有 n 个城市 m 条双向道路，每条道路连接了两个不同的城市。寒假到了，小 S 决定出门旅游一趟。因为以往跟团旅游多了，这次小 S 决定自驾游。对于自驾游，小 S 最关心的自然是燃油的耗费，为了省钱，小 S 请你帮他找一条最短的路。

输入格式:

第一行两个整数 n,m，表示有 n 个城市和 m 条双向道路。城市从 1..n 编号。 接下来 m 行，每行三个正整数 a,b,c，表示 a 和 b 之间有一条长为 c 的双向道路。a,b 不相同，且 c 不超过 1000

注意：两个城市之间可能会有多条双向道路。 接下来一行两个整数，s,t，表示小 S 本次旅行的出发地和目的地。s,t 不相同。

输出格式:

仅一行一个整数，表示最短的距离。如果不能到达，请输出-1。

样例输入:

3 3 1 2 1 1 3 3 2 3 1 1 3

样例输出:

2

提示:

【样例解释】

1->2->3 即是最优解。

【数据范围】

对于 30%的数据，n<=100,m<=1000

对于 100%的数据，n<=2000,m<=100000

时间限制: 1000ms

空间限制: 128MB

下面是本蒟蒟的代码：

#include<bits/stdc++.h>
using namespace std;
struct data1{
    int val,id;
};
struct data2{
    int to,val;
};
priority_queue<data1>q;
int n,m,s,t,ans[2005],fa[5005];
vector<data2>a[2005];
bool operator<(data1 x,data1 y){
	return x.val>y.val;
}
int find(int x){
	if(fa[x]==x)return x;
	return fa[x]=find(fa[x]);
}
void unin(int x,int y){
	if(find(x)!=find(y))fa[find(x)]=find(y);
}
bool check(int x,int y){
	return find(x)==find(y);
}
int main(){
    scanf("%d%d",&n,&m);
    int x,y,z;
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        a[x].push_back({y,z});
        a[y].push_back({x,z});
        unin(x,y);
    }
    scanf("%d%d",&s,&t);
    if(!check(s,t)){
    	printf("-1");
    	return 0;
	}
    memset(ans,0x3f3f,sizeof(ans));
    ans[s]=0;
    q.push({ans[s],s});
    for(int i=1;i<=n*2;i++){
        data1 top=q.top();
        q.pop();
        for(int j=0;j<a[top.id].size();j++){
            data2 v=a[top.id][j];
            if(ans[v.to]!=0x3f3f){
                ans[v.to]=min(ans[v.to],top.val+v.val);
            }
            else{
                ans[v.to]=top.val+v.val;
            }
            q.push({ans[v.to],v.to});
        }
    }
    printf("%d",ans[t]);
    return 0;
}

求dalao相助！