1、信使

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,m;
int g[N][N];
int dist[N];
bool st[N];
const int INF=0x3f3f3f3f;int dij(){memset(dist,0x3f,sizeof dist);dist[1]=0;for(int i=1;i<n;i++){int t=0;for(int j=1;j<=n;j++){if(!st[j]&&dist[j]<dist[t]){t=j;}}st[t]=true;for(int k=1;k<=n;k++){dist[k]=min(dist[k],dist[t]+g[t][k]);}}int res=0;for(int i=1;i<=n;i++){if(dist[i]==INF) return -1;res=max(res,dist[i]);}return res;
}int main(){cin>>n>>m;memset(g,0x3f,sizeof g);for(int i=1;i<=n;i++){g[i][i]=0;}for(int i=0;i<m;i++){int u,v,w;cin>>u>>v>>w;g[u][v]=min(g[u][v],w);g[v][u]=min(g[v][u],w);} cout<<dij()<<endl;return 0;
}

2、最小花費

#include<bits/stdc++.h>
using namespace std;
const int N=2005;
double g[N][N];
double dist[N];
bool st[N];
int n,m,A,B;
void dij(){memset(st, 0, sizeof st);st[N]={0.0};dist[A]=1.0;for(int i=1;i<=n;i++){int t=-1;for(int j=1;j<=n;j++){if(!st[j]&&(t==-1||dist[j]>dist[t])){t=j;}}if(t==0)continue;st[t]=true;for(int k=1;k<=n;k++){if(g[t][k]>0){dist[k]=max(dist[k],dist[t]*g[t][k]);}	}}
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){g[i][j]=0;}}for(int i=1;i<=n;i++){int u,v,w;cin>>u>>v>>w;double r=(100.0-w)/100.0;g[u][v]=max(g[u][v],r);g[v][u]=max(g[u][v],r);}cin>>A>>B;dij();cout<<fixed<<setprecision(8)<<100.0/dist[B]<<endl;return 0;
}

3、Dijkstra算法（模板）

#include<bits/stdc++.h>
using namespace std;
const int N=2505;
int g[N][N];
int dis[N];
bool vis[N];
int n, m, s, t;
const int INF=1e9+10;void dij(int start, int end) {// 初始化距離數組for(int i=1; i<=n; i++) {dis[i] = INF;vis[i] = false;}dis[start] = 0;for(int i=1; i<=n; i++) {int u = -1, min_dist = INF;// 尋找未訪問節點中距離最小的節點for(int j=1; j<=n; j++) {if(!vis[j] && dis[j] < min_dist) {min_dist = dis[j];u = j;}}if(u == -1) break; // 所有可達節點都已處理vis[u] = true; // 標記節點為已訪問// 更新鄰接節點的距離for(int v=1; v<=n; v++) {if(!vis[v] && g[u][v] != INF && dis[u] + g[u][v] < dis[v]) {dis[v] = dis[u] + g[u][v];}}}
}int main() {cin >> n >> m >> s >> t;// 初始化鄰接矩陣for(int i=1; i<=n; i++) {for(int j=1; j<=n; j++) {if(i == j) g[i][j] = 0;else g[i][j] = INF; // 無邊的情況初始化為INF}}// 讀取邊for(int i=1; i<=m; i++) {int u, v, w;cin >> u >> v >> w;// 處理重邊，取最小值g[u][v] = min(g[u][v], w);g[v][u] = min(g[v][u], w);}dij(s, t);cout << dis[t] << endl; // 輸出最短路徑return 0;
}

4、排列論文

#include<bits/stdc++.h>
using namespace std;
const int N=105;
vector<int>g[N];
int a[N];
int n,m;
int flag;
int topSort(){queue<int>q;for(int i=1;i<=n;i++){if(a[i]==0){q.push(i);}}int cnt=0;//記錄拓撲排序的排點數flag=1;while(!q.empty()){int t=q.front();q.pop();cnt++;if(!q.empty())flag=2;for(int i=0;i<g[t].size();i++){int x=g[t][i];a[x]--;if(a[x]==0)q.push(x);}}if(cnt<n)flag=0;return flag; 
}
int main() {while(cin>>n>>m){for(int i=1;i<=n;i++){//初始化 g[i].clear();//每一個點清空 a[i]=0;}for(int i=1;i<=m;i++){int u,v;cin>>u>>v;a[v]++;//更新入度 g[u].push_back(v);}int ff=topSort();if(ff==0)cout<<"0\n";else if(ff==1)cout<<"1\n";else if(ff==2)cout<<"2\n";}return 0;
}