HDU - 2680 Choose the best route（超级源点，反向建边，Dijkstra）

HDU - 2680 Choose the best route

Dijkstra算法，有两种方法：

1.是反向建边，把起点当作终点，终点看成起点，然后反向建边。

2.建立一个超级源点，将这个源点与其他起点距离为0，然后走一次Dijkstra算法就好

#include<cstdio>
#include<cstring>
const int N = 1010, INF=0x3f3f3f3f;
int e[N][N],dis[N],vis[N];
int n,m,s;
void Dijkstra()
{
    memset(vis,0,sizeof vis);for(int i=1;i<=n;i++) dis[i]=e[s][i];dis[s]=0;for(int i=1;i<=n;i++){
    int minn=INF,u;for(int j=1;j<=n;j++){
    if(!vis[j]&&minn>dis[j]){
    u=j;minn=dis[j];}}vis[u]=1;for(int j=1;j<=n;j++)if(!vis[j]&&dis[j]>dis[u]+e[u][j])dis[j]=dis[u]+e[u][j];} int w,minn=INF;scanf("%d",&w);while(w--){
    int start;scanf("%d",&start);if(dis[start]<minn) minn=dis[start];}if(minn==INF) printf("-1\n");else printf("%d\n",minn);
}
int main()
{
    while(scanf("%d%d%d",&n,&m,&s)!=EOF){
    memset(e,INF,sizeof e);while(m--){
    int p,q,t;scanf("%d%d%d",&p,&q,&t);if(t<e[q][p]) e[q][p]=t;}Dijkstra();}return 0;
} 

#include<cstdio>
#include<cstring>
const int N = 1010, INF=0x3f3f3f3f;
int e[N][N],dis[N],vis[N];
int n,m,s;
void Dijkstra()
{
    memset(vis,0,sizeof vis);for(int i=0;i<=n;i++) dis[i]=e[0][i];dis[0]=0;for(int i=0;i<=n;i++){
    int minn=INF,u;for(int j=1;j<=n;j++){
    if(!vis[j]&&minn>dis[j]){
    u=j;minn=dis[j];}}vis[u]=1;for(int j=1;j<=n;j++)if(!vis[j]&&dis[j]>dis[u]+e[u][j])dis[j]=dis[u]+e[u][j];} if(dis[s]==INF) printf("-1\n");else printf("%d\n",dis[s]);
}
int main()
{
    while(scanf("%d%d%d",&n,&m,&s)!=EOF){
    memset(e,INF,sizeof e);while(m--){
    int p,q,t;scanf("%d%d%d",&p,&q,&t);if(t<e[p][q]) e[p][q]=t;}int w;scanf("%d",&w);while(w--){
    int start;scanf("%d",&start);e[0][start]=0;}Dijkstra();}return 0;
}