思路:最短路+SPFA
分析:
1 题目要求的是从某一个站点能否到达目标站点
2 题目的其实站点有多个,如果都对每一个站点进行SPFA的话那么肯定TLE的。所以这个时候我们想到了增加一个新的点0,用来作为新的起点。这个时候只要把能够和0相连的点的权值标记为0即可。
3 注意这一题的图是一个有向图
代码:
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<queue> using namespace std; #define MAXN 1010 #define INF 0xFFFFFFF int n , m , s , k; int value[MAXN][MAXN]; int map[MAXN][MAXN]; int dis[MAXN]; int vis[MAXN]; queue<int>q; void input(){ int a , b , v; for(int i = 0 ; i <= n ; i++){ for(int j = 0 ; j <= n ; j++) value[i][j] = INF; value[i][i] = 0; } for(int i = 0 ; i < m ; i++){ scanf("%d%d%d" , &a , &b , &v); map[a][b] = 1; if(value[a][b] > v) value[a][b] = v; } scanf("%d" , &k); for(int i = 0 ; i < k ; i++){ scanf("%d" , &a); value[0][a] = 0;/*标记为0*/ map[0][a] = 1; } } void SPFA(){ memset(vis , 0 , sizeof(vis)); for(int i = 1 ; i <= n ; i++) dis[i] = INF; dis[0] = 0; vis[0] = 1; q.push(0); while(!q.empty()){ int x = q.front(); q.pop(); vis[x] = 0; for(int i = 1 ; i <= n ; i++){ if(map[x][i] && dis[i] > dis[x] + value[x][i]){ dis[i] = dis[x] + value[x][i]; if(!vis[i]){ q.push(i); vis[i] = 1; } } } } } int main(){ while(scanf("%d%d%d" , &n , &m , &s) != EOF){ input(); SPFA(); if(dis[s] != INF) printf("%d\n" , dis[s]); else printf("-1\n"); } return 0; }