拓扑排序
# include<iostream>
# include<cstring>
using namespace std;const int N=10000;int topoq[N];
int n,m;
int d[N]={0};
int e[N],ne[N],h[N],idx=0;void add(int a,int b){e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}bool toposort(){int hh=0,tt=-1;for(int i=1;i<=n;i++)if(!d[i])topoq[++tt]=i;while(hh<=tt){int t=topoq[hh++];for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(--d[j]==0)topoq[++tt]=j;}}return tt==n-1;
}int main(){memset(h,-1,sizeof h);cin>>n>>m;for(int i=0;i<m;i++){int s,t;scanf("%d%d",&s,&t);add(s+1,t+1);d[t+1]++;}if(toposort()){for(int i=0;i<n;i++){printf("%d",topoq[i]-1);if(i!=n-1)printf(" ");}}else{cout<<-1;}return 0;
}
dijkstra
# include<iostream>
# include<cstring>
# define INF 0x3f3f3f3f;
using namespace std;
const int N=510;
int g[N][N];
int dist[N];
bool st[N];
int n,m;int dijkstra(){memset(dist,0x3f,sizeof dist);dist[1]=0;for(int i=0;i<n-1;i++){int t=-1;for(int j=1;j<n;j++){if(!st[j]&&(t==-1||dist[j]<dist[t])){t=j;}}for(int j=1;j<=n;j++){dist[j]=min(dist[j],dist[t]+g[t][j]);st[t]=true;}}if(dist[n]==0x3f3f3f3f) return -1;return dist[n];
}int main(){memset(g,0x3f,sizeof g);cin>>n>>m;for(int i=0;i<m;i++){int s,t,w;scanf("%d%d%d",&s,&t,&w);g[s][t]=w;}cout<<dijkstra();
}
)
