http://acm.hdu.edu.cn/showproblem.php?pid=2680&&Choose theベストロute
図の最も短絡的な問題があって、ピットのお父さん、図のコードに提出していないで後でWAにn回行った後に、また注意深く一回の問題を見て、もとは向図があって、杯具.
もう一つの注意が必要なのは、逆思考のために、図は逆に存在し、覚え、
ACコード:
もう一つの注意が必要なのは、逆思考のために、図は逆に存在し、覚え、
ACコード:
#include<iostream>
#include<string.h>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#define N 1010
#define MAX 999999999
using namespace std;
struct Gnode
{
Gnode(){};
Gnode(int num,int len):num(num),len(len){}
int num;
int len;
};
int dis[N];
typedef pair<int,int> pii;
int n,m,s;
void in(int &a)
{
char ch;
while((ch=getchar())<'0'||ch>'9');
for(a=0;ch>='0'&&ch<='9';ch=getchar()) a=a*10+ch-'0';
}
void Dijstra(vector<vector<Gnode> >&Graph)
{
priority_queue<pii,vector<pii>,greater<pii> >Q;
for(int i=1;i<=n;++i) dis[i]=(i==s)?0:MAX;
Q.push(make_pair(dis[s],s));
while(!Q.empty())
{
pii cur=Q.top();
Q.pop();
int v=cur.second;
if(cur.first!=dis[v]) continue;
for(int i=0;i<Graph[v].size();++i)
{
int u=Graph[v][i].num;
int len=Graph[v][i].len;
if(dis[v]+len<dis[u])
{
dis[u]=dis[v]+len;
Q.push(make_pair(dis[u],u));
}
}
}
}
int main()
{
while(~scanf("%d%d%d",&n,&m,&s))
{
vector<vector<Gnode> >Graph(n+5);
for(int i=0;i!=m;++i)
{
int a,b,c;
in(a),in(b),in(c);
Graph[b].push_back(Gnode(a,c));
}
Dijstra(Graph);
int t;
in(t);
int ans=MAX;
for(int i=0;i!=t;++i)
{
int a;
in(a);
if(ans>dis[a]) ans=dis[a];
}
if(ans==MAX) printf("-1
");
else printf("%d
",ans);
}return 0;
}
隣接行列+優先列:#include<queue>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
using namespace std;
#define N 1005
#define MAX 999999999
int map[N][N], LowCost[N], n, m, s;
bool flag[N];
void in(int &a)
{
char ch;
while((ch=getchar())<'0'||ch>'9');
for(a=0;ch>='0'&&ch<='9';ch=getchar()) a=a*10+ch-'0';
}
struct POW{
int i,v;
friend bool operator<(POW a,POW b)
{
return a.v>b.v;
}
};
void Dijkstra(){
priority_queue<POW>Q;
POW temp ;
for(int i=1 ; i<=n ; i++){
flag[i] = 0;
LowCost[i] =(i==s)?0:map[s][i];
temp.i = i;
temp.v =LowCost[i];
Q.push(temp);
}
int num=0;
while(!Q.empty())
{
POW cur=Q.top();
Q.pop();
int v=cur.v;
int k=cur.i;
if(flag[k]) continue;
if(v==MAX||num==n-1) break;
flag[k]=1;
num++;
for(int j=1; j<=n; j++ )
if(!flag[j] && (map[k][j]+v) < LowCost[j] ){
LowCost[j] = map[k][j] + v ;
temp.i =j;
temp.v = LowCost[j];
Q.push(temp);
}
}
}
void Init(){
for(int i=1 ; i<=n ; i++ )
for(int j=1 ; j<=n ; j++ )
map[i][j]=MAX;
}
int main(){
int i, x, y, weight;
while( ~scanf("%d" , &n)){
in(m),in(s);
Init();
for( i=0 ; i<m ; i++ ){
in(x),in(y),in(weight);
if(map[y][x]>weight) map[y][x]=weight;
}
Dijkstra();
int w ,start;
in(w);
int Min = MAX;
for( i=0 ; i<w ; i++){
in(start);
if (Min > LowCost[start])
Min=LowCost[start];
}
printf("%d
", Min==MAX?-1:Min );
}
return 0 ;
}