PIPIOJ 1286: PIPI运货 最短路径

题目：

http://39.106.164.46/problem.php?id=1286

代码如下：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<vector>
#define MAX 105
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;int n,m,q,s,t;
int vis[MAX],dis[MAX],mp[MAX][MAX],cost[MAX];void dijkstra(int s){
    memset(dis,INF,sizeof(dis));memset(vis,0,sizeof(vis));dis[s]=0;for(int i=0;i<n;i++){
    int u=-1,minl=INF;for(int j=1;j<=n;j++){
    if(vis[j]==0&&dis[j]<minl){
    u=j;minl=dis[j];}}if(u==-1) break;vis[u]=1;for(int v=1;v<=n;v++){
    if(vis[v]==0&&mp[u][v]!=INF){
    if(dis[v]>dis[u]+mp[u][v]+cost[u]){
    dis[v]=dis[u]+mp[u][v]+cost[u];}}}}
}int main(){
    memset(mp,INF,sizeof(mp));scanf("%d",&n);int len;for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
    scanf("%d",&len);if(len>0) mp[i][j]=len;}}for(int i=1;i<=n;i++){
    scanf("%d",&cost[i]);}scanf("%d",&q);for(int i=0;i<q;i++){
    scanf("%d %d",&s,&t);int tmp1=cost[s],tmp2=cost[t];cost[s]=0,cost[t]=0;dijkstra(s);cost[s]=tmp1,cost[t]=tmp2;printf("%d\n",dis[t]);}return 0;
}