hdu 1874 畅通project续
最短路问题，尽管a!=b,可是同一条路測评数据会给你非常多个。因此在读入的时候要去最短的那条路存起来………见了鬼了。坑爹
#include<iostream>
#include<vector>
#include<cstring>
#define maxn 205
#define inf 1<<30
using namespace std;
int n,m;
int vaule[maxn][maxn];
vector<int>mapp[maxn];
int visit[maxn];
int a,b;
int dijkstra()
{int d[maxn];fill(d,d+n,inf);fill(visit,visit+n,0);d[a]=0;while(!visit[b]){int v=-1;for(int i=0;i<n;i++){if(!visit[i]&&(v==-1||d[i]<d[v])) v=i;}visit[v]=1;for(int i=0;i<mapp[v].size();i++){int x=mapp[v][i];d[x]=min(d[x],vaule[v][x]+d[v]);//cout<<x<<"~"<<d[x]<<"~"<<endl;}}if(d[b]==inf) return -1;return d[b];
}
int main()
{while(cin>>n>>m){for(int i=0;i<=n;i++) mapp[i].clear();memset(vaule,0,sizeof(vaule));for(int i=0;i<m;i++){int x,y,z;cin>>x>>y>>z;if(x!=y&&!vaule[x][y]){mapp[x].push_back(y);mapp[y].push_back(x);vaule[x][y]=z;vaule[y][x]=z;}else {vaule[x][y]=min(vaule[x][y],z);vaule[y][x]=min(vaule[y][x],z);}}cin>>a>>b;cout<<dijkstra()<<endl;}return 0;
} posted on 2017-05-29 09:02 mthoutai 阅读(…) 评论(…) 编辑 收藏
转载于:https://www.cnblogs.com/mthoutai/p/6917293.html