Tram

这里其实没有必要使用SPFA算法，但是为了巩固知识，还是用了。也可以使用dijikstra算法。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int INF=0X3F3F3F3F;
const int maxn=102;
int n,a,b;
int map[maxn][maxn];
bool vis[maxn];
int d[maxn];
struct edge{
    int to;
    int cost;
};
vector<edge> edges[maxn];
void SPFA(int s){
    memset(vis,0,sizeof(vis));
    vis[s]=1;
    queue<int> q;
    memset(d,INF,sizeof(d));
    d[s]=0;
    q.push(s);
    while(!q.empty()){
        int v=q.front();
        q.pop();
        vis[v]=0;
        for(int j=0;j<edges[v].size();j++){
            edge e=edges[v][j];
            int u=e.to;
            int cost=e.cost;
            if(d[u]>d[v]+cost){
                d[u]=d[v]+cost;
                if(!vis[u]){
                    q.push(u);
                    vis[u]=1;
                }
            }
        }
    }
}
int main(){
    while(cin>>n>>a>>b){
        for(int i=1;i<=n;i++){
            int k;
            cin>>k;
            for(int j=1;j<=k;j++){
                int te;
                cin>>te;
                if(j==1){
                    edges[i].push_back({te,0});
                    map[i][te]=0;
                }else {
                    map[i][te]=1;
                    edges[i].push_back({te,1});
                }
            }
        }
        SPFA(a);
        if(d[b]==INF)
            cout<<-1<<endl;
        else
            cout<<d[b]<<endl;
    }
    return 0;
}

java:

package POJ;
import java.util.*;
import java.io.*;
public class POJ_1847 {
    static int n,a,b;
    static final int INF=0X3F3F3F3F;
    static class edge{
        int to;
        int cost;
        edge(){}
        edge(int to,int cost){
            this.to=to;
            this.cost=cost;
        }
    };
    static Vector<edge>[] ed;
    static int []d;
    static class node implements Comparable<node>{
        int to;
        int dis;
        node(){}
        node(int to,int dis){
            this.to=to;
            this.dis=dis;
        }
        @Override
        public int compareTo(node t) {//默认小根堆，越小优先级越大
            // TODO Auto-generated method stub
            if(dis<t.dis)
                return -1;
            else if(dis>t.dis)
                return 1;
            else return 0;
        }

    };
    static void dijkstra(int s) {
        PriorityQueue<node>que=new PriorityQueue<node>();
        que.add(new node(s,0));
        Arrays.fill(d, INF);
        d[s]=0;
        while(!que.isEmpty()) {
            node temp=que.poll();
            if(d[temp.to]<temp.dis)
                continue;
            for(int i=0;i<ed[temp.to].size();i++) {
                edge e=ed[temp.to].elementAt(i);
                if(d[e.to]>d[temp.to]+e.cost) {
                    d[e.to]=d[temp.to]+e.cost;
                    que.add(new node(e.to,d[e.to]));
                }
            }
        }
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner cin=new Scanner(System.in);
        n=cin.nextInt();
        a=cin.nextInt();
        b=cin.nextInt();
        ed=new Vector[n+1];
        for(int i=0;i<=n;i++) {
            ed[i]=new Vector<edge>();
        }
        d=new int[n+1];
        for(int i=1;i<=n;i++) {
            int k;
            k=cin.nextInt();
            for(int j=0;j<k;j++) {
                int temp;
                temp=cin.nextInt();
                if(j==0) {//默认指向的方向
                    ed[i].add(new edge(temp,0));
                }else {
                    ed[i].add(new edge(temp,1));
                }
            }
        }
        dijkstra(a);
        if(d[b]==INF)
            System.out.println(-1);
        else System.out.println(d[b]);
    }

}